lp2147 SDOI2008 洞穴勘测

维护链接和断开,LCT裸题,(看起来)也可以用按秩合并优化并查集。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>


inline void Swap(int &A,int &B){
	A^=B^=A^=B;
} 
const int N=10005;

int fa[N],ch[N][2],rev[N]; 

inline void updt(int X){
	return;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		flp(ch[X][0]),flp(ch[X][1]);
		rev[X]=0;
	}
}
inline int ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
}
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
int n,q;
char op[20]; 
void init(){
	scanf("%d%d",&n,&q);
	int x,y;
	for(int i=1;i<=q;++i){
		std::cin>>op;
		scanf("%d%d",&x,&y);
		switch(op[0]){
			case 'C':{
				link(x,y);
				break;
			}
			case 'D':{
				cut(x,y);
				break;
			}
			case 'Q':{
				chgrt(x);
				puts(qryrt(y)==x?"Yes":"No");
				break;
			}
		}
	} 
}
int main(){
	init();
	return 0;
}

lp3690 【模板】Link Cut Tree (动态树)

树链剖分有多种方法。例如以重量为关键字的重链剖分,以长度为关键字的长链剖分。
而LCT(Link-Cut-Tree)就是一种特殊的利用Splay维护树的剖分结构的算法。
我们称一棵树上连接同一条链的边为实边,连接不同的链的边为虚边,那么这棵树就被分成了许多链。我们称这种剖分方法为实链剖分。
由于实链剖分的虚实是可以动态变化的,因此它具有很多用途。比如动态维护连通性、换根等等操作。
下面我们大致地考虑如何用Splay维护LCT实现实链剖分。

对于实链剖分剖出的每一条链,它总是一条自上往下的链。形式化地说,链中的节点的深度连续且各不相同。
对于原树剖分出的每一条链,我们建一棵Splay维护这棵树。每个点在Splay上的权值是这个点在原树上的深度。这样,无论Splay的结构如何改变,这棵Splay始终维护的是一条链。
对于每棵Splay,我们设它的父亲为整个链的最顶端节点的父亲。
对于原树中的一条实边,由于它位于Splay中,所以它对应着Splay中的一组前驱-后继关系。
对于原树中的一条虚边,它连接的两个节点中的一个节点对应的是两条链之间的连接。位于较下方的那条链对应的Splay的父亲显然指向的是位于较上方的那个节点;而位于较上方的那个节点却不必指向位于较下方的那个节点。这条性质被称为「认父不认子」。

access(Y)
显然,在维护信息的时候,原图上的实链结构并不总是能让我们满意。这时候我们需要从根到Y将树上的某一条竖直的链变成实链,并且不改变它原来的性质。这要怎么做呢?
我们设计一个access(接驳)函数,来完成这个过程。
对于路径上的第一条需要变成实边的虚边,我们是容易找到的——这便是Y所在的Splay的根节点连向其父亲的边。当然,这需要我们将Y旋到其所在的Splay的根。
我们将Y所在的Splay的根的父亲A也旋到其所在的Splay的根,那么它原本的实子链在Splay上正好是它的右子树。所以,我们将它的右子节点改为Y节点。那么,A-Y是已经成为了一条满足操作要求的实链,于是问题就转化为了将A-X转化为实链的子问题。
于是依次向上修改即可。

chgrt(X)
在实际操作中,我们操作的链并不总是从某个节点到根的一条链。这时候我们需要换根操作。
首先,我们将根节点到将要成为根的节点X置于同一条实链上——这可以通过access来达成。
在access后,X便是X所在的Splay中原树深度最浅的节点,也就是最右的节点。这时候,倘若将X旋到其所在的Splay的根,然后翻转X,那么整条链就上下倒转了。

qryrt(X)
在确认连通性的时候,我们需要询问某个点X所在的树的根。
显然,这要求的就是access之后X所在的Splay的最左端节点。

split(X,Y)
在处理具体操作的时候,我们可能会需要将某一条链摘离出来。
如果它们连通,只需要换根到一者,然后access另一者即可。

link(X,Y)
从X到Y连边。
方法很简单,将X作为它所在的树的根,然后直接连一条虚边即可。

cut(X,Y)
删除X和Y之间的边。
倘若保证X和Y之间本来是有连边的,那倒是容易了,直接split出来之后分离两者即可。
现在我们需要考虑两者没有连边的情况。
首先,我们将X变为根,然后寻找Y的根。
考虑Splay操作的影响,我们知道,这样操作之后,在Splay树上,Y节点一定在X节点的右儿子的位置。
在这种情况下,如果Y的根不是X,那么显然两者不连通。如果Y不是X的后继,那么显然两者之间有隔着点,也就不是父子关系。

注意:
一:关于Splay:在LCT中,我习惯使用的SplayOne的方法并不是特别有效,这是因为在LCT中存在虚边。
二:在旋转的时候,需要特别注意判断C是空节点和Y是根节点的情况。在这两种情况下有两句话是不应该写的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=300005;
int fa[N],ch[N][2],rev[N],sm[N],val[N];

inline bool isrt(int X){
	return ch[fa[X]][0]!=X&&ch[fa[X]][1]!=X;
}
inline void updt(int X){
	sm[X]=sm[ch[X][0]]^sm[ch[X][1]]^val[X];
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		if(ch[X][0]){
			flp(ch[X][0]);
		}
		if(ch[X][1]){
			flp(ch[X][1]);
		}
		rev[X]=0;
	}
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
//	int D=fndD(X),D2=fndD(fa[X]);
//	fa[ch[X][D^1]]=fa[X],ch[fa[X]][D]=ch[X][D^1];
//	ch[X][D^1]=fa[X],fa[X]=fa[ch[X][D^1]];
//	ch[fa[X]][D2]=X,fa[ch[X][D^1]]=X;
//	updt(ch[X][D^1]),updt(X);
//	在LCT中,我习惯使用的SplayOne的方法并不是特别有效,这是因为在LCT中存在虚边。
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(fa[X]),C=ch[X][D^1];
	if(!isrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[X]=Z,fa[Y]=X;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(!isrt(Y)){
		Y=fa[Y];
		st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(!isrt(X)){
		Y=fa[X],Z=fa[Y];
		if(!isrt(Y)){
			splayOne((fndD(X)^fndD(Y))?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
} 
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
} 
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
int n,q;
void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		sm[i]=val[i];
	}
	int op,x,y;
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&op,&x,&y);
		switch(op){
			case 0:{
				split(x,y);
				printf("%d\n",sm[y]);
				break;
			}
			case 1:{
				link(x,y);
				break;
			}
			case 2:{
				cut(x,y);
				break;
			}
			case 3:{
				splay(x);
				val[x]=y;
				updt(x);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp3676 小清新数据结构题

仔细考虑这道题,我们可以将问题转化为「修改」和「换根」两个操作。
对于修改操作,我们知道,每个点的权值对且仅对它到根节点上的这一条链上的每个点的答案产生贡献。
我们不妨令以1为根的情况下的每个点的修改前子树权值和为\(a_{i}\),修改对权值的改变为\(dlt\),那么可以计算得:
$$ans’=\sum(a_{i}+dlt)^2=\sum a_{i}^2+2dlt\times a_{i}+dlt^2\times len$$
故而,我们只需要用树链剖分套线段树维护树上区间平方和即可。

接下来我们考虑换根操作。
我们假设根从1换到了\(x\),那么子树权值大小会发生改变的仅有这条路径经过的点。我们不妨令换根后它们的子树权值和为\(b_{i}\),并有1~x为这条路径构成的序列,则我们发现答案会做出如下变动:
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+\sum_{i=x}^1 b_{i}^2$$
我们发现,路径上的相邻点的子树的并集构成了整棵树。这也就意味着:
$$a_{i}+b_{i+1}=a_{0}=b_{x}$$
于是我们可以依此得到:
$$ans’=ans-\sum_{i=x}^1 a_{i}^2+b_x^2+\sum_{i=x-1}^1 (a_{0}-a_{i+1})^2$$
$$ans’=ans-\sum_{i=x}^2 a_{i}^2+(len-1)\times a_{0}^2-2a_{0}\times\sum_{i=x-1}^1 a_{i+1}+\sum_{i=x}^2a_{i}^2$$
$$ans’=(len-1)a_0^2-2a_{0}\sum_{i=x}^2a_{i}$$
同样也可以用树链剖分套线段树维护树上区间和与区间平方和。
注意:树剖不要写挂,下传给重儿子的链顶应该是本节点的链顶。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
typedef long long ll;

inline char rdc() {
 	static char buf[10000000], *p = buf, *end = buf;
	if (p == end) end = buf + fread(p = buf, sizeof(char), 10000000, stdin);
	return *(p++);
}

inline int rd(){
	int RT=0,c,f=1;
	while(!isdigit(c=rdc())){if(c=='-'){f=-1;}}
	do{RT=RT*10+c-'0';}while(isdigit(c=rdc()));
	return RT*f;
}

struct ee{
	int v;
	int nxt;
}e[400005];
int h[200005],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,q;
ll val[200005],sm[200005];
int fa[200005],dep[200005],tp[200005],sn[200005],sz[200005];
int dfn[200005],loc[200005],cnt=0;

inline void dfs0(int X,int FA){
	dep[X]=dep[FA]+1;
	fa[X]=FA;
	sz[X]=1;
	sm[X]=val[X];
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sm[X]+=sm[e[i].v];
	}
}

inline void dfs1(int X,int TP){
	loc[dfn[X]=++cnt]=X;
	tp[X]=TP;
	if(sn[X]){
		dfs1(sn[X],TP);
		//这里下传的应该是TP而非X...
		//树剖写挂了,我SB 
	}
	Fv(i,X){
		if(e[i].v==fa[X]||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,e[i].v);
	}
}
#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
struct data{
	ll sm;
	ll sm2;
	ll lzy;
}tr[2000005];

inline void rnw(int X,int Len,ll K){
	tr[X].sm2+=(K*K*Len+tr[X].sm*K*2);
	tr[X].sm+=(Len*K);
	tr[X].lzy+=K;
}
inline void pshd(int X,int L,int R){
	rnw(LS,LLEN,tr[X].lzy),rnw(RS,RLEN,tr[X].lzy);
	tr[X].lzy=0;
}
inline void updt(int X){
	tr[X].sm=tr[LS].sm+tr[RS].sm;
	tr[X].sm2=tr[LS].sm2+tr[RS].sm2;
}
inline void chg(int X,int L,int R,int A,int B,int V){
	if(L>=A&&R<=B){
		rnw(X,LEN,V);
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		chg(LS,L,MID,A,B,V);
	}
	if(B>MID){
		chg(RS,MID+1,R,A,B,V);
	}
	updt(X);
}
inline ll qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm;
	}
	if(L>B||R<A||B<A){
		return 0;
	}
	pshd(X,L,R);
	return qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);
}
inline ll qrySm2(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm2;
	}
	if(L>B||R<A||B<A){
		return 0;
	}
	pshd(X,L,R);
	return qrySm2(LS,L,MID,A,B)+qrySm2(RS,MID+1,R,A,B);
}
inline void build(int X,int L,int R){
	if(L==R){
		tr[X].sm=sm[loc[L]];
		tr[X].sm2=tr[X].sm*tr[X].sm;
		return;
	}
	build(LS,L,MID);build(RS,MID+1,R);
	updt(X);
}

void init(){
	n=rd(),q=rd();
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	for(int i=1;i<=n;++i){
		val[i]=rd();
	}
	dfs0(1,0);
	dfs1(1,1);
	build(1,1,n);
	int op,x,y;
	ll ans,a0=sm[1],sma,len;
	for(int i=1;i<=q;++i){
		op=rd();
		if(op==1){
			x=rd(),y=rd();
			y-=val[x];
			val[x]+=y;
			a0+=y;
			while(x){
				chg(1,1,n,dfn[tp[x]],dfn[x],y);
				x=fa[tp[x]];
			}
		}else{
			x=rd();
			len=sma=ans=0;
			ans=qrySm2(1,1,n,1,n);
			while(tp[x]!=tp[1]){
				len+=dfn[x]-dfn[tp[x]]+1;
				sma+=qrySm(1,1,n,dfn[tp[x]],dfn[x]);
				x=fa[tp[x]];
			}
			len+=dfn[x]-dfn[1];
			sma+=qrySm(1,1,n,dfn[1]+1,dfn[x]);
			printf("%lld\n",ans+a0*(len*a0-2*sma));
		}
	}
}
int main(){
	init();
	return 0;
}

lp2664 树上游戏

一种\(n^2log^2n\)的做法是可以想到的:点分治,使用multiset来维护以某个节点为根的某一些链上的颜色信息。合并的时候\(O(nlogn)\)合并。
我们略微计算了一下复杂度,感觉这是卡不过去的。

仔细想想我们发现计算一条路径上不同的颜色数量是较为困难的,故而我们可以转而统计不同颜色对\(ans_i\)的贡献。
我们仔细思考,发现,对于以一个点\(rt\)为根的子树的某个点\(i\),其颜色是从\(i\)到\(rt\)的路径上首次出现的,那么我们在计算任意一个其他子树内的点\(j\)答案时,可以将答案减去\(sz_i\),然后再容斥掉\(j\)到\(rt\)路径上存在\(a_i\)这种颜色的情况。
故而,对于每一次分治要处理的以\(rt\)为根的树,我们可以先预处理出\(sm\),表示的是这棵树中所有满足「到根节点路径上没有与其颜色相同的点」的点的子树大小之和;以及\(val_i\),表示的是颜色为\(i\)的到根节点路上没有颜色为\(i\)的节点的子树大小之和。然后我们需要对以它的每一个子节点为根的子树统计答案。
显而易见的,\(j\)到\(rt\)的路径上经过的颜色是不应该被重复统计的,所以我们要让\(sm\)减去\(\sum val_{i}\),其中\(i\)是路径上经过的颜色。
此外,我们还需要统计这些颜色对答案的贡献。令这些颜色的数量为\(nm\),那么它们对\(j\)的答案的贡献就应该是\(nm*dlt\),其中\(dlt\)是\(rt\)除了当前正在找的子节点以外的子节点的子树大小之和。
然后,我们还需要统计以根节点为路径端点的答案数量——这种答案是上述方法未统计到的。所以,我们需要将根节点的答案减去\(val_{a_{rt}}\),然后再加上以根节点为根的所有路径数量,也就是\(sz_{rt}\)

#include<iostream>
#include<cstdio>
#include<set>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)

typedef long long ll;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline ll Max(ll A,ll B){
	return A>B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,a[100005];
int s,rt=0;
int vis[100005];
ll sz[100005],mx[100005],ans[100005];
inline void dfs0(int X,int FA){
	sz[X]=1,mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],s-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
	}
}
ll cnt[100005],val[100005],sm=0,nm=0,dlt;
inline void dfs2(int X,int FA){
	sz[X]=1;
	++cnt[a[X]];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs2(e[i].v,X);
		sz[X]+=sz[e[i].v];
	}
	if(cnt[a[X]]==1){
		sm+=sz[X];
		val[a[X]]+=sz[X];
	}
	--cnt[a[X]];
}
inline void dfs3(int X,int FA,int TYP){
	++cnt[a[X]];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs3(e[i].v,X,TYP);
	}
	if(cnt[a[X]]==1){
		sm+=sz[X]*TYP;
		val[a[X]]+=sz[X]*TYP;
	}
	--cnt[a[X]];
}
inline void dfs4(int X,int FA){
	++cnt[a[X]];
	if(cnt[a[X]]==1){
		++nm;
		sm-=val[a[X]];
	}
	ans[X]+=sm+nm*dlt;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs4(e[i].v,X);
	}
	if(cnt[a[X]]==1){
		--nm;
		sm+=val[a[X]]; 
	}
	--cnt[a[X]];
}
inline void dfs5(int X,int FA){
	val[a[X]]=cnt[a[X]]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs5(e[i].v,X);
	}
}
inline void calc(int X){
	sm=nm=0;
	dfs2(X,0);
	ans[rt]+=sm-val[a[X]]+sz[X];
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		++cnt[a[X]];
		sm-=sz[e[i].v];
		val[a[X]]-=sz[e[i].v];
		dfs3(e[i].v,X,-1);
		--cnt[a[X]];
		
		dlt=sz[X]-sz[e[i].v];
		dfs4(e[i].v,X);
		
		++cnt[a[X]];
		sm+=sz[e[i].v];
		val[a[X]]+=sz[e[i].v]; 
		dfs3(e[i].v,X,1);
		--cnt[a[X]];
	}
	dfs5(X,0);
}

inline void dfs1(int X){
	vis[X]=1;
	calc(X);
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		s=sz[X],rt=0;
		dfs0(e[i].v,X);
		dfs1(rt);
	}
}

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	rt=0,mx[0]=n;
	dfs0(1,0);
	dfs1(rt);
	for(int i=1;i<=n;++i){
		printf("%lld\n",ans[i]);
	}
}

int main(){
	init();
	return 0;
}

lp2634 国家集训队 聪聪可可

这一题本质上和那道「模板 点分治1」是一样的,直接一边统计一边取模即可。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

typedef long long ll;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline ll gcd(ll A,ll B){
	return B?gcd(B,A%B):A;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[20005],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,W);
}

int n,rt=0,s;
int vis[20005],sz[20005],mx[20005];
inline void dfs0(int X,int FA){
	sz[X]=1,mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],s-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
	}
}
int exist[3],dis[20005],st[20005],st2[20005],tp=0,tp2=0;
ll ans=0;
inline void dfs2(int X,int FA){
	st[++tp]=dis[X];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dis[e[i].v]=dis[X]+e[i].w;
		dfs2(e[i].v,X);
	}
}
inline void calc(int X){
	tp2=0;
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		tp=0;
		dis[e[i].v]=e[i].w;
		dfs2(e[i].v,X);
		for(int j=1;j<=tp;++j){
			ans+=exist[(3-st[j]%3)%3];
		}
		for(int j=1;j<=tp;++j){
			st2[++tp2]=st[j];
			++exist[st[j]%3];
		}
	}
	for(int i=0;i<3;++i){
		exist[i]=0;
	}
}

inline void dfs1(int X){
	exist[0]=vis[X]=1;
	calc(X);
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		rt=0;
		s=sz[X];
		dfs0(e[i].v,X);
		dfs1(rt);
	}
}

void init(){
	scanf("%d",&n);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	} 
	rt=0,mx[0]=n;
	dfs0(1,0);
	dfs1(1);
	ans=(ans<<1)+n;
	ll g=gcd(ans,n*n);
	printf("%lld/%lld\n",ans/g,(n*n)/g);
}

int main(){
	init();
	return 0;
}

lp3806 【模板】点分治1

点分治是一种常常用于处理树上路径统计问题的算法。
首先我们可以想到这一题的一种简单的分治做法:找到一个点,从它开始搜,求出它的每一种长度。然后搜它的每一个子树,找到这些子树的根,求出它们的每一种长度并统计答案。
下面的问题便是要如何统计答案。容易想到的一种方案是枚举以某个点为根的链长两两相加得到的长度再容斥掉重复经过某一条边的路径,也就是所有经过它的同一个子节点的链对。
然而仔细想想这种做法的复杂度是有问题的。在菊花图上,它甚至会达到\(n^2\)的复杂度。故而我们必须另外考虑其他做法。
仔细观察数据范围,我们发现询问个数不超过100,这启发我们考虑一种\(O(nmlogn)\)的做法。
当我们求出以某个节点为根且经过前\(i\)个子节点的所有链以后,我们可以直接标记这这些长度的存在性,然后搜索经过第\(i+1\)个子节点的所有链,并枚举判断询问的长度减去这个链的长度剩下的长度是否存在。
这就做完了。

另:这题的数据是真的水。我犯了两个错,一个是没重设为局部大小,一个是找重心写挂了,而且用的还是复杂度错的算法,居然还过了…

#include<iostream>
#include<cstdio>

#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

inline int Max(int A,int B){
	return A>B?A:B;
}
struct ee{
	int v;
	int w;
	int nxt;
}e[20005];
int h[10005],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);Eadd(V,U,W);
}
int ans[10005]; 

int n,m,rt,s;

int mx[10005],sz[10005],vis[10005];
inline void dfs0(int X,int FA){
	sz[X]=1,mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],s-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
	}
}
int a[10005];
int dis[10005],tp=0;
inline void dfs2(int X,int FA){
	dis[++tp]=a[X];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		a[e[i].v]=a[X]+e[i].w;
		dfs2(e[i].v,X);
	}
}
int exist[10000005],lst[10005],cnt=0,qry[10005];
inline void calc(int X){
	cnt=0;
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		a[e[i].v]=e[i].w;
		tp=0;
		dfs2(e[i].v,X);
		for(int j=1;j<=m;++j){
			for(int k=1;k<=tp;++k){
				(qry[j]-dis[k]>=0)?ans[j]|=exist[qry[j]-dis[k]]:0; 
			}
		}
		for(int j=1;j<=tp;++j){
			lst[++cnt]=dis[j];
			exist[dis[j]]=1;
		}
	}
	for(int i=1;i<=cnt;++i){
		exist[lst[i]]=0;
	}
}

inline void dfs1(int X){
	exist[0]=vis[X]=1;
	calc(X);
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		s=sz[X],rt=0;//记得重置根。 
		dfs0(e[i].v,X);
		dfs1(rt);
	}
}

void init(){
	scanf("%d%d",&n,&m);
	int u,v,w,x;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		qry[i]=x;
	}
	s=n,mx[0]=n,rt=0;
	dfs0(1,0);
	dfs1(rt);
	for(int i=1;i<=m;++i){
		puts(ans[i]?"AYE":"NAY");
	}
} 

int main(){
	init();
	return 0;
}

lp5236 【模板】静态仙人掌(圆方树)

按照我们之前的经验,仙人掌上问题往往可以通过圆方树转化为树上问题。
我们发现,最短路在树上是一种非常容易解决的问题。只需预处理到根节点的长度然后死命跑LCA就可以了。
但是在一般图上,最短路的实时处理就会变得很困难。
我们可以尝试通过给圆方树上的边赋上特别的边权来处理这个问题。

对于圆-圆边,赋边权为原边权,这是容易理解的。
对于方点到它的父亲圆点的边,赋边权为0,对于圆点到它的父亲方点的边,赋边权为这个圆点到这个方点的父亲圆点的最短距离。

这时候我们会遇到一个问题,就是Tarjan找环的时候找不到返祖边的边权。
解决方案是记录每一个到根节点在dfs树上的距离,然后当我们找到一个环一路找爸爸并统计长度即可。

然后是计算答案,我们发现,如果询问的两个点的最近公共祖先是一个方点,那么它们的答案不能用普通方法计算。
我一开始的想法是尝试直接用某个节点到父亲方点的边权直接计算答案,但这样会导致答案错误,原因是它无法正确地区分两个点位于圆环的同一侧还是不同侧的情况。
故而,我们需要保存原来的距离它的父亲方点的靠某一侧的距离,故而当lca是方点的时候特殊判断计算即可。

 #include<iostream>
#include<cstdio>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

typedef long long ll;

inline ll Min(ll A,ll B){
    return A<B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline ll Abs(ll A){
	return A>0?A:-A;
}
inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}

struct ee{
    int v;
    ll w;
    int nxt;
}e[200005];
int h0[10005],h[20005],et=0;
inline void Eadd(int *H,int U,int V,ll W){
    e[++et]=(ee){V,W,H[U]};
    H[U]=et;
}
inline void add(int *H,int U,int V,ll W){
    Eadd(H,U,V,W);
    Eadd(H,V,U,W);
}
int dfn[20005],lw[20005],cnt=0,dep[20005],fa[20005][30];
ll dis[20005],sz[20005];
int nm=0;
int st[20005],tp=0;
inline void dfs0(int X){
    dfn[X]=lw[X]=++cnt;
    Fv(h0,i,X){
    	if(e[i].v==fa[X][0]){
    		continue;
		}
        if(!dfn[e[i].v]){
            fa[e[i].v][0]=X;
            dis[e[i].v]=dis[X]+e[i].w;
            dfs0(e[i].v);
            lw[X]=Min(lw[X],lw[e[i].v]);
    	}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
			if(e[i].v!=fa[X][0]&&dfn[e[i].v]<dfn[X]){
                ++nm;
                add(h,nm,e[i].v,0);
                ll len=e[i].w;
                for(int j=X;j^e[i].v;j=fa[j][0]){
                	len+=dis[j]-dis[fa[j][0]];
                }
                sz[nm]=len;
                ll nw=e[i].w;
                for(int j=X;j^e[i].v;j=fa[j][0]){
                    add(h,nm,j,Min(nw,len-nw));
                    sz[j]=nw; 
                    nw+=dis[j]-dis[fa[j][0]];
                }
            }
        }
        if(lw[e[i].v]>dfn[X]){
        	add(h,X,e[i].v,e[i].w);
		} 
    }
}

inline void dfs1(int X,int FA){
    dep[X]=dep[FA]+1;
    fa[X][0]=FA;
    Fv(h,i,X){
        if(e[i].v!=FA){
            dis[e[i].v]=dis[X]+e[i].w;
            dfs1(e[i].v,X);
        }
    }
}

int n,m,q;

inline ll calc(int X,int Y){
    int XX=X,YY=Y,lca;
    while(dep[XX]<dep[YY]){
        Swap(XX,YY);
    }
    for(int i=20;~i;--i){
        if(dep[XX]-(1<<i)>=dep[YY]){
            XX=fa[XX][i];
        }
    }
    if(XX==YY){
        lca=XX;
    }else{
        for(int i=20;~i;--i){
            if(fa[XX][i]!=fa[YY][i]){
                XX=fa[XX][i];
                YY=fa[YY][i];
            }
        }
        lca=fa[XX][0];
    }
    ll RT=dis[X]+dis[Y]-(dis[lca]<<1);
    if(lca>n){
        ll P=dis[XX]-dis[lca],Q=dis[YY]-dis[lca];
        RT-=(P+Q);
        RT+=Min(sz[lca]-Abs(sz[XX]-sz[YY]),Abs(sz[XX]-sz[YY]));
    }
    return RT;
}



void init(){
    scanf("%d%d%d",&n,&m,&q);
    nm=n;
    int u,v;
	ll w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%lld",&u,&v,&w);
        add(h0,u,v,w);
    }
    fa[1][0]=0;
    dfs0(1);
    for(int i=1;i<=nm;++i){
        dep[i]=0,dis[i]=0;
    }
    dfs1(1,0);
    for(int j=1;j<=20;++j){
        for(int i=1;i<=nm;++i){
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
    int x,y;
    for(int i=1;i<=q;++i){
        scanf("%d%d",&x,&y);
        printf("%lld\n",calc(x,y));
    }
}
int main(){
    init();
    return 0;
}

lp3320 SDOI2015 寻宝游戏

我们找到了这样一个结论:
「一个树上点集构成的最小生成树中,若两点间有路径,则此两点的DFS序在树上相近。」
这个结论的证明是较为困难的,但是感性理解还是比较容易的。
有了这个结论,我们就可以解决这一题。
每当一个新的点x即将加入点集的时候,我们只需要计算点集中DFS序刚好比它小的点y和DFS序刚好比它大的点z,然后将答案加上如下的式子:
$$dis_{x,y}+dis_{x,z}-dis_{y,z}$$
删去的时候逆向操作即可。
维护点集可以使用set。(善用STL(大雾))计算路径长度可以LCA+容斥。

注意:记得开long long

#include<iostream>
#include<cstdio>
#include<set>

struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
int fa[100005][30],dfn[100005],loc[100005],dep[100005],cnt=0;
long long val[100005];
//注意将两种深度分开。 
inline void dfs(int X,int FA){
	fa[X][0]=FA,dfn[X]=++cnt,loc[cnt]=X,dep[X]=dep[FA]+1;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			val[e[i].v]=val[X]+e[i].w;
			dfs(e[i].v,X);
		}
	}
}

inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		std::swap(X,Y);
	}
	for(int i=20;i>=0;--i){
		if(dep[X]-(1<<i)>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=20;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i];
			Y=fa[Y][i];
		}
	}
	return fa[X][0];
}

inline long long dis(int X,int Y){
	return val[X]+val[Y]-(val[lca(X,Y)]<<1);
}

int n,m;
long long ans=0;
bool vis[100005];
std::set<int> s;
void init(){
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,0);
	for(int j=1;j<=20;++j){
		for(int i=1;i<=n;++i){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	int x,y,z;
	long long d;
	std::set<int>::iterator it;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		x=dfn[x];
		if(!vis[loc[x]]){
			s.insert(x);
		}
		y=loc[(it=s.lower_bound(x))==s.begin()?*--s.end():*--it];
		z=loc[(it=s.upper_bound(x))==s.end()?*s.begin():*it];
		//注意运算符优先级。 
		if(vis[loc[x]]){
			s.erase(x);
		}
		x=loc[x];
		d=dis(x,y)+dis(x,z)-dis(y,z);
		if(!vis[x]){
			vis[x]=1;
			ans+=d;
		}else{
			vis[x]=0;
			ans-=d;
		}
		//注意前后的x不是一个x 
		printf("%lld\n",ans);
	}
}

int main(){
	init();
	return 0;
}

CF487E Tourists

众所周知,圆方树是用来处理图上点双相关问题的。
同时,点双又是一个和简单路径密切相关的东西。故而这一题我们可以考虑用圆方树来处理。
我们发现,如果两点之间有多条简单路径,那么它们一定处于同一个点双中。所以,我们可以把原图转化为圆方树,这样就可以用树链剖分套线段树来求解询问了。
但是题目要求要修改点权,这要怎么办呢?

一个直观的想法是暴力修改每个点周围相邻的方点。然而事实上如果出现了个菊花套菊花套菊花图的话显然是会严重TLE的。
我们考虑一种动态维护一个方点的点值的算法。我们尝试对每个方点开一个mulitiset,每当修改一个点的点权的时候就把旧的点权删去然后插入新的点权,并更新方点点值。
然而,如果每个修改的圆点周围都有很多的方点的话,这种做法仍然有TLE的风险。我们考虑对于每个圆点,只更新它的父亲方点。
它对它的儿子方点的贡献,则在询问的时候统计。
这样复杂度就对了。
这就使用了圆方树上树链剖分套线段树解决了这道题。

注意:
树链剖分中更新最大孩子的部分,这里是son!不是sz!调了我一个晚上!

#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<set>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

std::multiset<int> s[200005]; 

const int INF=2147483647;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}

struct ee{
	int v;
	int nxt;
}e[2000005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}


int dfn[200005],lw[100005];
//注意数组大小。 
int nm,cnt=0;
int st[100005],tp=0;
inline void dfs0(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
				++nm;
				for(int j=0;j!=e[i].v;--tp){
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}
int fa[200005],sz[200005],dep[200005],son[200005],top[200005],loc[200005];
inline void dfs1(int X,int FA){
	fa[X]=FA,dep[X]=dep[FA]+1,sz[X]=1;
	Fv(h,i,X){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
			sz[X]+=sz[e[i].v];
			if(sz[son[X]]<sz[e[i].v]){
				son[X]=e[i].v;
				//这里是son!不是sz!调了我一个晚上! 
			}
		}
	}
}
inline void dfs2(int X,int FA,int TP){
	dfn[X]=++cnt,loc[cnt]=X,top[X]=TP;
	if(son[X]){
		dfs2(son[X],X,TP);
	}
	Fv(h,i,X){
		if(e[i].v!=FA&&e[i].v!=son[X]){
			dfs2(e[i].v,X,e[i].v);
		}
	}
}

int n,m,q;
int a[200005];

#define MID (L+R>>1)
#define LS (X<<1)
#define RS (X<<1|1)

int tr[600005];
inline void bld(int X,int L,int R){
	if(L==R){
		tr[X]=a[loc[L]];
//		记得逆哈希 
		return;
	}
	bld(LS,L,MID);
	bld(RS,MID+1,R);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	tr[X]=Min(tr[LS],tr[RS]);
}

inline int qry(int X,int L,int R,int A,int B){
	if(A>R||L>B){
		return INF;
	}
	if(A<=L&&R<=B){
		return tr[X];
	}
	return Min(qry(LS,L,MID,A,B),qry(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d%d%d",&n,&m,&q);
	nm=n;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	dfs0(1);
	dfs1(1,0);
	cnt=0;
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		if(fa[i]){
			s[fa[i]].insert(a[i]);
		}
	}
	for(int i=n+1;i<=nm;++i){
		a[i]=*s[i].begin();
	}
	
	bld(1,1,nm);
	char ch[3];
	int x,y;
	int ans;
	
	for(int i=1;i<=q;++i){
		scanf("%s%d%d",ch,&x,&y);
		if(ch[0]=='C'){
			chg(1,1,nm,dfn[x],y);
			if(fa[x]){
				u=fa[x];
				s[u].erase(s[u].lower_bound(a[x]));
				s[u].insert(y);
				if(a[u]!=*s[u].begin()){
					a[u]=*s[u].begin();
					chg(1,1,nm,dfn[u],a[u]);
				}
			}
			a[x]=y;
		}else{
			ans=INF;
			while(top[x]!=top[y]){
				if(dep[top[x]]<dep[top[y]]){
					Swap(x,y);
				}
				ans=Min(ans,qry(1,1,nm,dfn[top[x]],dfn[x]));
				x=fa[top[x]];
			}
			if(dfn[x]>dfn[y]){
				Swap(x,y);
			}
			ans=Min(ans,qry(1,1,nm,dfn[x],dfn[y]));
			if(x>n){
				ans=Min(ans,a[fa[x]]);
			}
			printf("%d\n",ans);
		}
	} 
}

int main(){
	init();
	return 0;
}

lp4630 APIO2018 Duathlon 铁人两项

圆方树是一种在仙人掌图上常用的数据结构,但是这并不意味着圆方树只在仙人掌图上有用。事实上,在任何一张图上,我们都可以用相似的方法来构造一棵圆方树。
对于一张图,我们预处理出它的所有点双,然后对每一个点双建一个方点,其他处理方法和仙人掌上圆方树几乎相同。
这里的点双要如何预处理呢?我们考虑一个性质:当我们预处理出一张图的DFS树后,任何一条边属于且仅属于一个点双。
那么,我们就可以尝试找到一个点双中深度最浅的节点,然后由它构造出这个方点。
我们发现,当我们搜索完一个节点的子树后,如果子节点中的某一个节点的lw是这个节点,那么这个节点就是它所在的点双中深度最浅的节点。
这是因为,如果一个节点的lw节点是它的父节点,那么它和它的子树就没有任何返祖边能够到达比当前节点更浅的节点,也就说明如果当前节点在点双内,那么它一定是点双内最浅的节点。
有没有可能当前节点不在点双内呢?这是不可能的。如果有返祖边连向当前节点,那么当前节点显然不会成为割点;如果没有,那么当前节点所属的点双就一定只有两个点。

现在把目光投到这道题。
首先考虑点双的基本性质。我们发现,对于至少有三个点的点双,任取三个点,它们总是一对满足题意的三元组。
这是由于点双的定义,点双里没有割点,自然总是可以找到两点间的两条不相交的简单路径。
拓展这个结论,我们发现,如果一条简单路径经过一个点双,那么显然无论固定哪个点,这条路径都始终是一条简单路径。
故而,对于选定的起点和终点,我们可以分两类讨论。
倘若它们位于同一个点双,那么显然它们之间的满足题意的三元组个数恰好是这个点双的点数-2
对于不属于同一个点双的情况,它们之间有可能经过其他的点双,也有可能不经过。每经过一个点双,它们之间的满足题意的三元组个数就会加上这个点双的点的个数。
同时,答案还要加上起点和终点各自处在的点双的点数个数各自-1。
这要怎么统计呢?我们可以让每个方点的权值为点双中的点的数量,每个圆点的权值为-1,然后枚举点对统计路径和即可。
仔细一想觉得有点不对劲儿:这样的复杂度岂不是要n^2logn级别?妥妥地T啊。
正难则反,我们可以统计每个点对答案的贡献,也就是经过它的路径数乘上它本身的权值。而前者可以通过一个普通的树形DP求得。
这就做完了。

注意:
要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小,而非总节点数减去它的子树大小。故而要注意统计连通块大小。

#include<iostream>
#include<cstdio>
#define Fv(H,A,X) for(int A=H[X];A;A=e[A].nxt)

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[1200005];
int h0[100005],h[200005],et=0;
inline void Eadd(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int *H,int U,int V){
	Eadd(H,U,V);
	Eadd(H,V,U);
}

int n,m;
int dfn[100005],lw[100005],cnt=0,nm=0;
int st[100005],tp=0;
int val[200005],nwsz;
long long ans=0;
inline void dfs(int X){
	dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	++nwsz;
//	要注意每个点的子树外的节点的数量是相当于连通块大小减去它的子树大小,而非总节点数减去它的子树大小。故而要注意统计连通块大小。 
	Fv(h0,i,X){
		if(!dfn[e[i].v]){
			dfs(e[i].v);
			lw[X]=Min(lw[X],lw[e[i].v]);
			if(lw[e[i].v]==dfn[X]){
//				注意这里应当判定的是lw(v)=dfn(u) 
				val[++nm]=1;
				for(int j=0;j!=e[i].v;--tp){
					++val[nm];
					j=st[tp];
					add(h,nm,j);
				}
				add(h,X,nm);
			}
		}else{
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
}

int vis[200005],sz[200005];

inline void dfs2(int X){
	vis[X]=1;
	sz[X]=(X<=n);
	Fv(h,i,X){
		if(!vis[e[i].v]){
			dfs2(e[i].v);
			ans+=2ll*val[X]*sz[X]*sz[e[i].v];
			sz[X]+=sz[e[i].v];
		}
	}
	ans+=2ll*val[X]*sz[X]*(nwsz-sz[X]);
}

void init(){
	scanf("%d%d",&n,&m);
	nm=n;
	for(int i=1;i<=n;++i){
		val[i]=-1;
	}
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(h0,u,v);
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			nwsz=0;
			dfs(i);
			dfs2(i);
			--tp;
		}
	}
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}

lp4244 SHOI2008 仙人掌图 II

仙人掌图是每一个点双都只有一个环的连通图。
对于一个仙人掌图,它在许多方面都有树的性质,只是其中的有一些节点被换成了环。
我们不妨依然采用一种伪树形DP的方式来处理这棵树,我们发现,非环节点的转移都是非常容易达成了,问题在于环上的节点的转移。

首先,我们要找到这个环,这可以用Tarjan算法来完成。
具体来说,我们维护两个数组:dfn和lw,其中前者表示的是某一个节点的dfs序,后者表示的是某一个节点至多走一条返祖边或者父亲边能够到达的最小dfs序。
显然,在搜索中,如果下一个节点未被访问过,我们就可以在搜索完它以后将当前节点的lw与它的lw取较小值。
否则,当前节点通向它的边一定是一条返祖边或者父亲边,那么当前节点的lw值应当与它的dfs序取较小值。

对于一个环,我们如果将它视为一个节点,我们想一想要怎么从它的「孩子」们处转移呢?
我们发现,依次枚举它的每一个孩子,答案显然是:
$$max(f_i+f_j+dis_{i,j})$$
这个式子可以使用单调队列优化。所以我们每一次把一个环提出来瞎DP一下就好了。

#include<iostream>
#include<cstdio>
#include<deque>
#define Fv(A,U) for(int A=h[U];A;A=e[A].nxt)

inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[200005];
int et=0,h[100005];
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,m;
int dfn[100005],lw[100005],dep[100005],fa[100005],cnt=0;
int ans=0,f[100005],a[100005];
std::deque<int> q;
inline void calc(int X,int Y){
	int tot=dep[Y]-dep[X]+1;
	int nw=tot;
	for(int i=Y;i!=X;i=fa[i]){
		a[nw--]=f[i];
	}
	a[nw]=f[X];
	for(int i=1;i<=tot;++i){
		a[tot+i]=a[i];
	}
	while(!q.empty()){
		q.pop_front();
	}
	q.push_back(1);
	for(int i=2;i<=(tot<<1);++i){
		while(!q.empty()&&i-q.front()>(tot>>1)){
			q.pop_front();
		}
		if(!q.empty()){
			ans=Max(ans,a[i]+a[q.front()]+i-q.front());
		}
		while(!q.empty()&&a[q.back()]-q.back()<a[i]-i){
			q.pop_back();
		}
		q.push_back(i);
	}
	for(int i=2;i<=tot;++i){
		f[X]=Max(f[X],a[i]+Min(i-1,tot-i+1));
	}
}
inline void dfs(int X,int FA){
	dfn[X]=lw[X]=++cnt;
	Fv(i,X){
		if(e[i].v!=FA){//这一句如果不加会无形降低很多点的lw值,从而使环的大小变成0。 
			if(!dfn[e[i].v]){
				fa[e[i].v]=X;
				dep[e[i].v]=dep[X]+1;
				dfs(e[i].v,X);
				lw[X]=Min(lw[X],lw[e[i].v]);
			}else{
				lw[X]=Min(lw[X],dfn[e[i].v]);
			}
			if(lw[e[i].v]>dfn[X]){
				ans=Max(ans,f[X]+f[e[i].v]+1);
				f[X]=Max(f[X],f[e[i].v]+1);
			}
		}
		
	}
	Fv(i,X){
		if(fa[e[i].v]!=X&&dfn[X]<dfn[e[i].v]){
			calc(X,e[i].v);
		}
	}
}

void init(){
	scanf("%d%d",&n,&m);
	int u,v,x;
	for(int i=1;i<=m;++i){
		u=0;
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d",&v);
			if(u){
				add(u,v);
			}
			u=v;
		}
	}
	dfs(1,0);
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp4382 八省联考2018 劈配

扫一眼题目,看到n个点和m个点匹配的问题,你就会有一种预感——是不是要跑二分图匹配?
是的,就是要跑二分图匹配。
第一问很显然,大力让一个导师能够被多个学生匹配,然后跑一个类似于匈牙利的操作。然后如果匹配满了,我们就考虑将这个导师匹配的其他学生尝试匹配同一个优先级的其他节点。
这个复杂度肯定是很松的。
那么关键在于第二问要怎么处理。
观察发现答案具有单调性。也就是说,如果一个选手在较高的优先度会感到沮丧,那么他在一个较低的优先度也会感到沮丧;
因此我们考虑二分答案来检验。
这样的复杂度大概是三方乘对数级的。时间比较紧张。
我们考虑一种优化策略:发现选手提高到某个优先度了以后,他就相当于顶替了本来在这个优先度的选手的位置。
故而,我们可以对于前缀的选手,储存到每个选手时的匹配状态。每次找到某个优先度,就把他的信息加入到对应的匹配状态中,然后跑上述操作。
这样可以优化到平方乘对数级,可能可以通过此题。
这一题的具体操作——也就是那个一点多匹配的操作并不是特别会,以后需要重新研究。
我好菜啊。

#include<iostream>
#include<cstdio>

int c,n,m;
int mx[205],a[205][205],val[205][205][15],exp[205];
int usd[205],usd1[205],usd2[205][205],vis[205];
int prusd[205][205],prusd1[205][205],prusd2[205][205][205];
inline bool dfs(int X,int V){
	int nw,nxt;
	for(int i=1;i<=val[X][V][0];++i){
		nw=val[X][V][i];
		if(vis[nw]){
			continue;
		}
		vis[nw]=1;
		if(usd[nw]<mx[nw]){
			usd1[X]=nw;
			usd2[nw][++usd[nw]]=X;
			return 1;
		}
		for(int j=1;j<=mx[nw];++j){
			nxt=usd2[nw][j];
			if(dfs(nxt,a[nxt][nw])){
				usd1[X]=nw;
				usd2[nw][j]=X;
				return 1;
			}
		}
	}
	return 0;
}
inline void calc1(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[j]=0;
		}
		for(int j=1;j<=m;++j){
			if(!val[i][j][0]){
				continue;
			}
			if(dfs(i,j)){
				break;
			}
		}
		for(int j=1;j<=m;++j){
			prusd[i][j]=usd[j];
		}
		for(int j=1;j<=i;++j){
			prusd1[i][j]=usd1[j];
		}
		for(int j=1;j<=m;++j){
			for(int k=1;k<=usd[j];++k){
				prusd2[i][j][k]=usd2[j][k];
			}
		}
	}
}
inline bool chck(int X,int Y){
	for(int i=1;i<=m;++i){
		usd[i]=prusd[Y-1][i];
	}
	for(int i=1;i<=Y-1;++i){
		usd1[i]=prusd1[Y-1][i];
	}
	for(int i=1;i<=m;++i){
		for(int j=1;j<=usd[i];++j){
			usd2[i][j]=prusd2[Y-1][i][j];
		}
	}
	for(int i=1;i<=m;++i){
		vis[i]=0;
	}
	for(int i=1;i<=exp[X];++i){
		if(!val[X][i][0]){
			continue;
		}
		if(dfs(X,i)){
			return 1;
		}
	}
	return 0;
}
void init(){
//	注意清空数组!!!
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d",&mx[i]);
	}
	for(int i=1;i<=200;++i){
		usd1[i]=0;
		usd[i]=0;
		for(int j=1;j<=200;++j){
			for(int k=0;k<=10;++k){
				val[i][j][k]=0;
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
			if(a[i][j]){
				val[i][a[i][j]][++val[i][a[i][j]][0]]=j;
			}
		}
	}
	for(int i=1;i<=n;++i){
		a[i][0]=m+1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&exp[i]);
	}
	calc1();
	for(int i=1;i<=n;++i){
		printf("%d ",a[i][usd1[i]]);
	}
	puts("");
	int l,r,mid,ans;
	for(int i=1;i<=n;++i){
		if(a[i][usd1[i]]<=exp[i]){
			printf("0 ");
			continue;
		}
		l=1,r=i-1,ans=0;
		while(l<=r){
			mid=(l+r)>>1;
			if(chck(i,mid)){
				ans=mid;
				l=mid+1;
			}else{
				r=mid-1;
			} 
		}
		printf("%d ",i-ans);
	}
	puts("");
}

int main(){
	int T;
	scanf("%d%d",&T,&c);
	while(T--){
		init();
	}
	return 0;
}

lp4363 九省联考2018 一双木棋chess

快要省选了,需要学习一些乱搞操作。
在这里学习一下Min-Max对抗搜索。
首先了解一下Min-Max对抗搜索。
首先我们知道,对于一个零和有限信息确定性博弈游戏,我们可以将整个游戏的所有局面建成一个有向图。而在几乎所有此类游戏中,整个游戏的所有局面应当能组成一个DAG。
对于这样一个DAG,我们可以对它进行分层,最后得到的应当是一张分层图。这张分层图上的每一层象征着一方正在进行操作。
那么显然这个游戏的最终解是可以知道的。无非就是直接把整张图DFS一遍罢了。
然而,在绝大部分游戏中,这么做的复杂度都太大了,以至于根本无法接受。我们考虑一种被称为Min-Max对抗搜索的搜索方法。
我们首先定义先手方为Max方,后手方为Min方,然后设置一个搜索范围。那么每一个节点的值是这样确定的:
如果它的深度是搜索深度边缘,亦或者它干脆就是一个终止局面,那么它的值就是一个精心设计的估价函数的值。这个估价函数应当能够较好地估计整个局面倾向于哪一方。
如果这个节点是由Max方行动,那么它的值是所有子局面里的值的最大值,因为Max方会向对自己最有利的局面走。
如果这个节点是由Min方行动,那么它的值是所有子局面里的值的最小值,因为Min方会向对Max方最不利的局面,也就是对自己最有利的局面走。
这样就能够求得当前局面的权值,从而得到一个较优秀的决策支了。
本来打算学一下alpha-beta剪枝的,但是这一题好像不是很需要…

回到这一题,如果我们暴力储存每一个状态,那么很显然时间会爆炸。有没有更好的思路呢?
直觉告诉我们,一个格子放置的次序和答案是没有关系的。所以我们不妨假定当前放置的格子总是左上角的一整个块。这样状态数大概就在10^10以内了。
然而实际上并不需要这么多的状态。所以可以Hash以后用map离散化。

#include<iostream>
#include<cstdio>
#include<tr1/unordered_map>

inline int Max(int A,int B){
	return A>B?A:B;
}

inline int Min(int A,int B){
	return A<B?A:B;
}
const int INF=0x3f3f3f3f;
std::tr1::unordered_map<long long,int> mp;
int a[11][11],b[11][11],f[11],n,m;

inline long long hsh(){
	long long RT=0;
	for(int i=1;i<=n;++i){
		RT*=12;
		RT+=f[i];
	}
	return RT;
}

inline void ahsh(long long X){
	for(int i=n;i>=1;--i){
		f[i]=X%12;
		X/=12;
	}
}

inline int dfs(long long X,bool typ){
	if(mp.count(X)){
		return mp[X];
	}
	int RT=typ?-INF:INF;
	long long nw;
	ahsh(X);
	for(int i=1;i<=n;++i){
		if(f[i]<f[i-1]){
			++f[i];nw=hsh();
			RT=typ?Max(RT,dfs(nw,0)+a[i][f[i]]):Min(RT,dfs(nw,1)-b[i][f[i]]);
			--f[i];
		}
	}
	return mp[X]=RT;
}

void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&b[i][j]);
		}
	}
	for(int i=0;i<=n;++i){
		f[i]=m;
	}
	mp[hsh()]=0;
	printf("%d\n",dfs(0,1));
}

int main(){
	init();
	return 0;
}

CF1131

这么早的CF已经很少见了,不过我还是大力掉分。
我好菜啊.jpg


CF1131A
观察题意,随便推个式子提交就AC了。
打卡题。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int a,b,c,d,ans=0;
void init(){
	scanf("%d%d%d%d",&a,&b,&c,&d);
	ans=a+b*2+c+d*2+std::abs(a-c)+4;
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1131B
一道比较简单的题,但是如果脑残了会非常难。
反正我脑残以后是瞎jb写了二十七个特判死活PP不了。
当然仔细理解题意会发现还是比较简单的——当且仅当上一个的终止状态是平局态的时候,答案会有额外的统计。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,a[100005],b[100005],ans=1;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&a[i],&b[i]);
		ans+=max(0,min(a[i],b[i])-max(a[i-1],b[i-1])+1);
		if(a[i-1]==b[i-1]){
			--ans;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1131C
比B简单,普通构造题。
第一个直观的感觉是从小到大排列,但是仔细想想觉得那样不一定更优。
所以考虑到FJ省冬令营ZZQ讲的构造技巧,可以上一个奇偶排序。
于是AC此题。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n,a[100005];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i+=2){
		printf("%d ",a[i]);
	} 
	for(int i=n;i>=1;--i){
		if(!(i&1)){
			printf("%d ",a[i]);
		}
	}
}
int main(){
	init();
	return 0;
}


CF1131D
一道细节题,车站分级弱化版。
如果没有等于号,直接拓扑排序就可以通过。
但是等于号比较蛋疼。
会发现等于号得到的东西都是相同等级的,所以可以考虑用并查集维护。
两个坑点:首先要考虑记录访问过的点的次数来判是否无解,因为可能存在一个独立的环。
然后更新答案应该要按照最后一个更新,而非第一个。这是由这个解法的基本特性,也就是解集是所有约束条件的并集这一特性决定的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n,m,in[2005];
char ch[1005][1005];

int f[2005];
inline int fa(int X){
	return f[X]==X?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	f[X]=Y;
}
bool mp[2005][2005];
queue<int> q;
bool vis[2005];
int ans[2005];
inline bool srt(){
	for(int i=1;i<=n+m;++i){
		if(!in[i]){
			q.push(i);
			ans[i]=1;
			vis[i]=1;
		}
	}
	int cnt=0; 
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		++cnt;
		for(int i=1;i<=n+m;++i){
			if(mp[p][i]){
				if(!in[fa(i)]){
					return 0;
				}else{
					--in[fa(i)];
					if(!in[fa(i)]){
						q.push(fa(i));
						ans[fa(i)]=min(ans[p]+1,ans[fa(i)]);
					}
				}
			}
		}
	}
	return cnt==n+m;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i]+1;
	}
	for(int i=1;i<=n+m;++i){
		f[i]=i,ans[i]=0x3f3f3f3f;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(ch[i][j]=='<'){
				mp[i][n+j]=1;
			}
			if(ch[i][j]=='>'){
				mp[n+j][i]=1;
			}
			if(ch[i][j]=='='){
				uni(i,n+j);
			}
		}
	}
	for(int i=1;i<=n+m;++i){
		if(fa(i)!=i){
			for(int j=1;j<=n+m;++j){
				mp[fa(i)][j]|=mp[i][j];
				mp[i][j]=0;
			}
			for(int j=1;j<=n+m;++j){
				if(mp[j][i]){
					mp[j][fa(i)]=1;
					mp[j][i]=0;
				}
			}
		}
	}
	for(int i=1;i<=n+m;++i){
		for(int j=1;j<=n+m;++j){
			if(mp[i][j]){
				++in[j];
			}
		}
	}
	if(!srt()){
		puts("No");
		return;
	}else{
		puts("Yes");
		for(int i=1;i<=n;++i){
			printf("%d ",ans[fa(i)]);
		}
		puts("");
		for(int i=n+1;i<=n+m;++i){
			printf("%d ",ans[fa(i)]);
		}
	}
	
	
}
int main(){
	init();
	return 0;
}


CF1131F
这道题和D题有一点神似。
我们维护每一个已经弄好的连续块的左端点和右端点,每次访问到这个块就直接连接到它的父亲。
这个过程用并查集完成,使得可以直接搜索到整个块的端点。每一次直接把前一个块接在后一个块的左边就好了。
把每个连接记录一下最后输出即可。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

struct ee{
	int v;
	int nxt;
}e[300005];
int h[150005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int n,l[150005],r[150005];
int f[150005];
inline int fa(int X){
	return X==f[X]?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	f[X]=Y;
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		l[i]=r[i]=i,f[i]=i;
	}
	int a,b;
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		a=fa(a),b=fa(b);
		add(r[a],l[b]);
		uni(a,b);
		l[b]=l[a];
	}
	a=l[fa(1)],b=0;
	printf("%d ",a);
	for(int i=1;i<n;++i){
		for(int j=h[a];j;j=e[j].nxt){
			if(e[j].v!=b){
				printf("%d ",e[j].v);
				b=a,a=e[j].v;
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp2597 ZJOI2012 灾难

这一题的思路还是比较清晰的。虽然可以当作支配树模板,但是事实上可以上一个LCA来代替支配树。
具体来说,就是把有多个食物的消费者连到它所有食物的LCA。然后计算一遍子树大小就好了。
注意连点之前要先拓扑排序。

#include<iostream>
#include<cstdio>
#include<queue>

#define Swap(A,B) (A^=B^=A^=B)

struct ee{
	int v;
	int nxt;
}e[2500005];
//h,树上的节点。g,拓扑排序的节点。to,每个节点的所有父亲。 
int h[70000],g[70000],et=0,dep[70000],fa[70000][18],in[70000],to[70000],sz[70000],loc[70000];
int n,tp=0;
inline void add(int *H,int U,int V){
	if(U==V){
		return;
	}
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void srt(){
	std::queue<int> q;
	for(int i=1;i<=n;++i){
		if(!in[i]){
			q.push(i);
		}
	}
	int p=0;
	while(!q.empty()){
		p=q.front();
		q.pop();
		loc[++tp]=p;
		for(int i=g[p];i;i=e[i].nxt){
			--in[e[i].v];
			if(!in[e[i].v]){
				q.push(e[i].v);
			}
		}
	}
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		Swap(X,Y);
	}
	for(int i=17;i>=0;--i){
		if(dep[X]-(1<<i)>=dep[Y]){
			X=fa[X][i]; 
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=17;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
inline void prpr(){
	int nw=0;
	for(int i=1,j;i<=n;++i){
		j=loc[i];
		nw=e[to[j]].v;
		for(int k=to[j];k;k=e[k].nxt){
			nw=lca(nw,e[k].v);
		}
//		请注意这里的nw可能不存在任何父亲节点。 
		add(h,nw,j);
		fa[j][0]=nw;
		dep[j]=dep[nw]+1;
		for(int k=1;k<=17;++k){
			fa[j][k]=fa[fa[j][k-1]][k-1];
		}
	}
}
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
		sz[X]+=sz[e[i].v];
	}
	++sz[X];
}
void init(){
	scanf("%d",&n);
	int x; 
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		while(x){
			++in[i];
			add(g,x,i);
			add(to,i,x);
			scanf("%d",&x);
		}
	}
	srt();
	prpr();
	dfs(0);
	for(int i=1;i<=n;++i){
		printf("%d\n",sz[i]-1);
	}
}

int main(){
	init();
	return 0;
}

lp2153 SDOI2009 晨跑

题意简述:求一张图上不共点两点间最大路径数。
首先考虑不共边最大路径数,很容易可以想到大力上一个最大流,边流量为一。
然后考虑不共点最大路径数。我们发现,可以通过拆点来构成约束条件。具体来说就是将每个点拆成入点和出点,然后跑一个网络流。
现在还要求一个最短总路径长度,很容易可以想到费用流。具体来说,就将每一条边的费用设置为它的长度。然后跑一遍即可。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[100005];
int h[405],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}

int n,m,s,t,dis[405],val[405],fa[405],nw[405];
bool vis[405];
std::queue<int> q;
inline int spfa(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(val[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}

void init(){
	scanf("%d%d",&n,&m);
	s=1,t=2*n;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v,c;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&c);
		add(n+u,v,1,c);
	}
	for(int i=2;i<n;++i){
		add(i,n+i,1,0);
	}
	add(1,n+1,1926,0);
	add(n,2*n,1926,0);
	int ansW=0,ansC=0,p;
	while(spfa()){
		p=t;
		ansW+=val[t];
		ansC+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
	printf("%d %d\n",ansW,ansC);
}

int main(){
	init();
	return 0;
}

lp2805 NOI2009 植物大战僵尸

仔细阅读题意,我们发现,这道题本质上就是一个约束类问题:对于每一株植物,都存在一些植物,需要消灭掉它们才能消灭它。
故而,它就变成了一个这样的问题:存在一些植物,其中的一些要消灭了另外一些之后才能消灭,问收益最大化的方法。
如果我们对每一棵植物建点,然后从一棵植物向它的约束植物连边,那么问题就转化为:一张有向图,每个点都有点权,请选中其中的某些点,使得每个点的后继都在这张图中。
这是一类被称为「最大权闭合子图问题」的问题。这种问题的解决方案是,从源点向正权点连权值为点权的边;从负权点向汇点连权值为点权的绝对值的边。原图中的边流量无穷大。
那么,答案就是总权值减去最小割。


下面我们来证明这种建模方式的合法性和最优性。
我们令从源点连出的边被割掉表示不选中这个点,连向汇点的边被割掉表示选中这个点。
那么,最终的结果必然是一个闭合子图。
这是因为,对于这张图的最小割,当你选中一个节点之后,这个点的所有后继负权节点都一定被割掉/选中了(根据割的性质显然);
这个点的所有后继正权节点都一定不被割/选中了(根据最小割的性质,割掉这些边没有意义)。
并且,任何一个闭合子图的选法都至少可以对应一个割法。
这是因为,对于原图中的某一种连接方法,都可以通过割掉不在其之中的所有负权边和在其之中的所有负权边来使其对应。
同时,根据我们此前的定义,最小割的值意味着没选中的正权点的值与选中的负权点的值的绝对值的和。故而,答案便是正权店的值的和减去最小割的值。
而最小割是要尽量小的,故而最小割可以得到最优答案。


PS:
这一题应当考虑死锁情况,想象一个无限攻击力和攻速的豌豆射手。(不考虑连样例都过不了)(但是尽管这样还是能够拿到80分)
具体处理方法就大力上一个拓扑排序即可。把所有需要缩掉的点打个标记,然后令这些点在网络流中不存在。
然而,如果我们直接写一个拓扑排序的话,还是只能得到80分的好成绩——这是因为这张图需要对反图进行拓扑排序。
细想,因为这张图上每一条有向边的终点一旦被删去,那么它的所有前驱也都是不能存在的。
故而,对反图进行拓扑排序找环并删去才能符合题目的要求。


#include<iostream>
#include<cstdio>
#include<queue>

const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

int n,m,s,t,nw[1005],dep[1005],val[1005];

struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[1005],et=-1,in[1005];
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
	++in[U];
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		nw[i]=h[i];
		if(dep[i]>-2){		
			dep[i]=INF;
		}
	}
	q.push(s);
	dep[s]=0;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;;
				q.push(e[i].v); 
			}
		}
	}
//	printf("%d\n",dep[t]);
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				} 
			}
		}
	}
	return cnt;
}

inline int calc(int X,int Y){
	return X*m+Y+1;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}
inline int srt(){
	for(int i=1;i<=t;++i){
		if(!in[i]){
			q.push(i);
		}
		dep[i]=-2;
	}
	int RT=0,p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		dep[p]=0;
		if(val[p]>0){
			RT+=val[p];
		}
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(!e[i].w){
				if(!--in[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
	return RT;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2,et=-1;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,y,z;
	for(int i=1;i<=n*m;++i){
		scanf("%d",&x);
		val[i]=x;
		x>0?(add(s,i,x),0):(x==0?0:(add(i,t,-x),0));
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d%d",&y,&z);
			add(calc(y,z),i,VERYBIG);
		}
		if(i%m){
			add(i,i+1,VERYBIG);
		}
	}
	int tot=srt();
	printf("%d\n",tot-dinic());
}

int main(){
	init();
	return 0;
}

lp2774 方格取数问题

这是一道最小割转最大流的例题。
首先,我们发现,这一题要求我们求的是所取和。然后容易知道,所取和等于总和减去舍弃和。
故而,我们要使得所取和最大,就只需要使得舍弃和最小。
尝试用所取和来建图并且跑最大流,发现,它并不是那么容易地建成一个可靠的图。
正难则反,我们考虑怎么样才能让舍弃和最小。
于是尝试用舍弃和最小来建图并且跑最小割。观察题目的性质我们发现,所有的坐标和的奇偶性相同的方格,永远是互不影响的。
这启发我们建一个二分图。
我们不妨将奇点建在左侧,偶点建在右侧。然后从源点向奇点连容量为数值的边;从偶点向汇点连容量为数值的边。
于是,很显然,当我们割掉任何一条边的时候,就意味着相应的点是不取的。
接着我们将相邻的黑白点连容量为无穷大的边,这意味着这两个点之间至少有一个不能取。
然后跑最大流得到最小割即可。

#include<iostream>
#include<cstdio>
#include<queue>


const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f; 

inline int Min(int A,int B){
	return A<B?A:B;
}


struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[40005],et=-1;
int dep[40005],nw[40005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int n,m,s,t;

inline int calc(int X,int Y){
	return (X-1)*m+Y;
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
			
		}
	}
	return cnt;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,cnt=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&x);
			cnt+=x;
			if((i+j)&1){
				add(s,calc(i,j),x);
				if(i+1<=n){
					add(calc(i,j),calc(i+1,j),VERYBIG);
				}
				if(i-1>=1){
					add(calc(i,j),calc(i-1,j),VERYBIG);
				}
				if(j+1<=m){
					add(calc(i,j),calc(i,j+1),VERYBIG);
				}
				if(j-1>=1){
					add(calc(i,j),calc(i,j-1),VERYBIG);	
				}
			}else{
				add(calc(i,j),t,x);
			} 
		}
	}
	printf("%d\n",cnt-dinic());
}

int main(){
	init();
	return 0;
}

lp1963 NOI2009 变换序列

如果知道这道题是一个二分图匹配,就显得非常简单了。
首先我们对原序列和变换序列各自建一个点。
然后,对于每一组约束条件\(D_{i}\),我们向所有到\(i\)的距离为\(D_{i}\)的点连一条边。
然后先跑一遍二分图最大匹配。如果全部都能匹配上就说明有解。

但是题目要求字典序输出这组解,怎么办呢?
这么做的意思就是,对于一个尽可能小的数\(i\),它匹配的数\(T_{i}\)也要尽可能小。
故而,搜索的时候从大往小即可。

#include<iostream>
#include<cstdio>
int n,D[10005];
int vis[10005],dep=0;
int usd[10005];

inline bool dfs(int X){
	int up=(X+D[X]-1)%n+1,dw=(X-D[X]+n-1)%n+1;
	if(up<dw){
		std::swap(up,dw);
	}
//	printf("%d %d\n",up,dw);
	if(!usd[dw]&&vis[dw]!=dep){
		vis[dw]=dep;
		usd[dw]=X;
		return 1;
	}
	if(vis[dw]!=dep){
		vis[dw]=dep;
		if(dfs(usd[dw])){
			usd[dw]=X;
			return 1;
		}
	}
	if(!usd[up]&&vis[up]!=dep){
		vis[up]=dep;
		usd[up]=X;
		return 1;
	}
	if(vis[up]!=dep){
		vis[up]=dep;
		if(dfs(usd[up])){
			usd[up]=X;
			return 1;
		}
	}
	
	return 0;
}
int Ans[10005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&D[i]);
	}
	int ans=0;
	for(int i=n;i>=1;--i){
		++dep;
		if(dfs(i)){
			++ans;
		}else{
			break;
		}
	}
	if(ans<n){
		puts("No Answer");
	}else{
		for(int i=1;i<=n;++i){
			Ans[usd[i]]=i;
		}
		for(int i=1;i<=n;++i){
			printf("%d ",Ans[i]-1);
		}
	}
}

int main(){
	init();
	return 0;
}

lp2764 网络流24题-最小路径覆盖问题


(其实建图方法已经写在题目里了。)
(这一题是一道匈牙利的裸题,考场上二分图最大匹配仍然建议使用匈牙利(因为在实现复杂度上有巨大优势),我纯粹练一下当前弧优化Dinic。)
首先有一个定理。将一张有向图上的每一个点都拆点成入点和出点,连边后形成一张二分图,那么原图的最小路径覆盖,就是顶点数减去这张二分图的最大匹配。
考虑感性地证明这个定理。
每一次匹配,事实上就意味着,一条路径可以额外走过一个点。这样就减少了一个路径覆盖。
所以,当匹配次数最大的时候,路径覆盖数就最小了。
答案用并查集处理一下输出。


#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[20005];
int h[2005],et=-1;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}
int dep[2005],nw[2005],f[2005];
int n,m,s,t;

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i; 
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

inline int fnd(int X){
	for(int i=h[X+n];i>=0;i=e[i].nxt){
		if(1<=e[i].v&&e[i].v<=n){
			if(e[i].w){
				return e[i].v;
			}
		}
	}
	return X;
}
inline int fa(int X){
	return f[X]^X?f[X]=fa(f[X]):X;
}
inline void prnt(int X){
	for(int i=h[X];i>=0;i=e[i].nxt){
		if((n+1)<=e[i].v&&e[i].v<=(n<<1)&&!e[i].w){
			printf("%d ",e[i].v-n
			);
			prnt(e[i].v-n);
			return;
		}
	}
}
bool vis[2005];
void init(){
	scanf("%d%d",&n,&m);
	s=(n<<1)+1,t=(n<<1)+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		add(s,i,1);
		add(n+i,t,1);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,n+v,1);
	}
	int ans=n;
	while(bfs()){
		ans-=dfs(s,INF);
	}
	for(int i=1;i<=n;++i){
		f[i]=i;
	}
	for(int i=1;i<=n;++i){
		f[i]=fnd(i);
	}
	for(int i=1;i<=n;++i){
		fa(i);
	}
	for(int i=1;i<=n;++i){
		if(f[i]==i){
			printf("%d ",i);
			prnt(i);
			puts("");
		}
	}
	printf("%d\n",ans); 
}

int main(){
	init();
	return 0;
}