lp2515 HAOI2010 软件安装

简单的tarjan缩点+树形背包DP。
考虑N<=100,M<=500,只需要设f[i][j]表示第i个点,已用j的容量。
然后直接DP即可。
特别地,由于如果某一个点的子树中的点被选中了,这个点也要被选中,所以我们在计算每个点的时候,一定要将这个点加进去。
然后仔细看看这道题,发现它不保证没有环!
这下完蛋了,咋做啊?
考虑到这个环要么都选,要么都不选,所以可以先用tarjan找环,把找环后的点拿来dfs。
然后我们考虑一个性质:如果存在环,那么这个环缩成的点一定是某一棵树的树根。
所以我们不妨计算每一个点的入度,然后将入度为0的点连向虚点0。这样只需要一次DP。

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

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[505];
int h[505],g[505],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
int n,m,f[505][505],w[505],v[505],ww[505],val[505],d[505],in[505];
int vis[505],clr[505],dfn[505],lw[505],cnt=0,ccnt=0,st[505],tp=0;
inline void dfs0(int X){
	vis[X]=1,dfn[X]=lw[X]=++cnt;
	st[++tp]=X;
	for(int i=g[X];i;i=e[i].nxt){
		if(!dfn[e[i].v]){
			dfs0(e[i].v);lw[X]=Min(lw[X],lw[e[i].v]);
		}else if(vis[e[i].v]){
			lw[X]=Min(lw[X],dfn[e[i].v]);
		}
	}
	if(dfn[X]==lw[X]){
		++ccnt;
		while(st[tp+1]!=X){
			clr[st[tp]]=ccnt;
			val[ccnt]+=v[st[tp]],ww[ccnt]+=w[st[tp]];
			vis[st[tp]]=0;
			--tp;
		}
	}
}
inline void dfs1(int X){
	for(int i=ww[X];i<=m;++i){
		f[X][i]=val[X];
	}
	for(int i=h[X];i;i=e[i].nxt){
		dfs1(e[i].v);
		for(int j=m-ww[X];j>=0;--j){//j表示之前的子树的重量和。 
			for(int k=0;k<=j;++k){//k表示这棵子树的重量和。 
				f[X][j+ww[X]]=Max(f[X][j+ww[X]],f[e[i].v][k]+f[X][j-k+ww[X]]); 
			}
		}
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&v[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
		if(d[i]){
			add(g,d[i],i);
		}
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			dfs0(i);
		}
	}
	for(int i=1;i<=n;++i){
		if(clr[d[i]]!=clr[i]){
			add(h,clr[d[i]],clr[i]);
			++in[clr[i]];
		}
	}
	for(int i=1;i<=ccnt;++i){
		if(!in[i]){
			add(h,0,i);
		}
	}
	dfs1(0);
	printf("%d\n",f[0][m]);
}
int main(){
	init();
	return 0;
}

lp3233 HNOI2014 世界树

让我们来分析这道题。
我们很容易地可以发现,如果一个节点是末端节点,那么它肯定是由它祖先中的第一个节点管辖更优。
由此我们继续推导,可以发现,假如只有两个关键点的话,它们之间的链上一定可以找到一个分界线,使得这条分界线的一段——以及所有与链上这一端相邻的节点——放在一个关键点上,并把剩下的放在另一个关键点上。这样是最优的。
然后我们考虑有三个关键点的情况。如果有三个关键点的话,问题似乎就复杂了很多,这是因为这条分界线必须是基于三个节点共同决定的。
我们换一个思路考虑。求出三个关键点两两的LCA。那么,这一分界线就必然可以在这六个点(最多六个)两两之间的链上找到。
存在一种叫做「虚树」的数据结构。这个数据结构本质上就是将所有关键点以及关键点两两之间的LCA建成一个数。
我们如此考虑,如果有一个点是关键点,那么它向下能够管辖的点的数量就是它的子树大小减去它的所有子节点能管辖的点数之和。
它向上能够管辖的点的数量则相对比较复杂。
我们考虑每一条边,假设我们已经预处理出了虚树上每一个点相邻最近的关键点,那么,如果这条边两端的点相邻最近的关键点是相同的,那么这条边(以及和这条边相邻的所有点)都划归到那个关键点下管辖。
如果这条边两段的点相邻最近的关键点不同,则需要使用倍增来确定这条边要如何被划分成两个部分。

接下来要考虑如何确定虚树上每一个点相邻最近的关键点。
我们不妨这样考虑:一个点相邻最近的关键点如果在它的下方,那么这可以通过树形DP求得;如果在它的上方或者其他子树内呢?
显然,如果这个点的相邻最近关键点在它的上方或者和它不在同一子树内,那么它的父亲的最近关键点一定与这个点的最近关键点相同。
于是,我们不妨从上而下DP,求得这个点在上方或者不在同一子树的最近关键点。

现在我们来梳理一下这一题的思路。
首先,我们进行预处理,处理出每个点的深度和dfn。
然后,我们进行两次树形DP,求出每个点的最近关键点。
第三,我们预处理出所有「末端节点」——也就是所有「是一个虚树上节点的直接儿子且子树内没有关键点的原树上的点」。这些点的贡献可以直接统计到它们父亲的最近关键点。
最后,我们依次考虑剩下的虚树边上的点。如果两段的最近关键点相同,那么就统计到那个最近关键点。否则就进行倍增寻找答案。

顺便讲一下如何建虚树。
我们将所有关键点按照dfs序排序,然后建一个栈,代表当前正在向下延长的链。
如果当前的点与栈顶的LCA的深度小等于次栈顶,那么就说明当前点不在栈顶的子树里,也就意味着栈顶处于当前应该维护的链外。
于是,我们需要就可以将新的这个点加入虚树和栈中。
否则,就说明原来的栈顶需要被弹出,那么就处理完它应该连的边然后将它弹出。

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

typedef pair<int,int> pii;
const int N=300005;
const int INF=0x3f3f3f3f;
struct ee{
	int v;
	int nxt;
}e[1200005];
int h[N],g[N],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}

int dfn[N],cnt=0,sz[N],dep[N],fa[N][20];
inline void dfs0(int X){
	dfn[X]=++cnt;sz[X]=1;
	Fv(i,X){
		if(e[i].v==fa[X][0]){
			continue;
		}
		fa[e[i].v][0]=X;dep[e[i].v]=dep[X]+1;
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
int usd[N],pt[N],ppt[N],hr[N],ans[N],up[N];
pii nr[N];
inline void dfs1(int X){
	nr[X]=(usd[X]?pii(0,X):pii(INF,0));
	Fv2(i,X){
		dfs1(e[i].v);
		nr[X]=min(nr[X],pii(nr[e[i].v].first+dep[e[i].v]-dep[X],nr[e[i].v].second));
	}
}
inline void dfs2(int X,int D,int P){
	if(pii(D,P)<nr[X]){
		nr[X]=pii(D,P);
	}else{
		D=nr[X].first,P=nr[X].second;	
	}
	Fv2(i,X){
		dfs2(e[i].v,D+dep[e[i].v]-dep[X],P);
	}
}
//子节点中所有子树中有虚树上节点的点都是不可以选取的。
//我们不妨逆向考虑,枚举每一个虚树上的子节点,然后从那个节点开始倍增,一直倍增到这棵树的子节点,然后把这些子节点的子树挖掉。 
inline void dfs3(int X){
	ans[hr[X]=nr[X].second]+=sz[X];
	Fv2(i,X){
		int nw=e[i].v;
		for(int j=18;j>=0;--j){
			if(fa[nw][j]&&dep[fa[nw][j]]>dep[X]){
				nw=fa[nw][j];
			}
		}
		ans[hr[X]]-=sz[up[e[i].v]=nw];
		dfs3(e[i].v);
	}
}
//现在剩下的末端节点就只有虚树上的节点了。 
//如果子节点的dfs序大于当前节点,那么分割点就偏上;否则偏下。 
inline void dfs4(int X){
	Fv2(i,X){
		if(hr[e[i].v]==hr[X]){
			ans[hr[X]]+=sz[up[e[i].v]]-sz[e[i].v];
		}else{
			int len=dep[hr[e[i].v]]+dep[X]-nr[X].first;
			len=((len&1)?(len+1)>>1:((len>>1)+(int)(hr[e[i].v]>hr[X])));
//			这里比较的是编号!!! 
			int nw=e[i].v;
			for(int j=18;j>=0;--j){
				if(dep[fa[nw][j]]>=len){
					nw=fa[nw][j];
				}
			}
			ans[hr[e[i].v]]+=sz[nw]-sz[e[i].v];
			ans[hr[X]]+=sz[up[e[i].v]]-sz[nw];
		}
		dfs4(e[i].v);
	}
}
inline void dfs5(int X){
	up[X]=hr[X]=0;
	Fv2(i,X){
		dfs5(e[i].v);
	}
	g[X]=0;
}
inline bool cmp(int A,int B){
	return dfn[A]<dfn[B];
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		swap(X,Y);
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int st[N],tp=0;
void init(){
	int n,Q;
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(h,u,v);
		add(h,v,u);
	}
	dep[1]=1;
	dfs0(1);
	for(int j=1;j<=18;++j){
		for(int i=1;i<=n;++i){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	scanf("%d",&Q);
	int m,X,Y;
	while(Q--){
		scanf("%d",&m);
		for(int i=1;i<=m;++i){
			scanf("%d",&pt[i]);
			ppt[i]=pt[i],usd[pt[i]]=1;
		}
		sort(pt+1,pt+1+m,cmp);
		st[tp=1]=pt[1];
		for(int i=2;i<=m;++i){
			X=pt[i],Y=lca(X,st[tp]);
			while(tp>1&&dep[Y]<=dep[st[tp-1]]){
				add(g,st[tp-1],st[tp]);
				--tp;
			}
			if(Y!=st[tp]){
				add(g,Y,st[tp]);st[tp]=Y;
			}
			st[++tp]=X;
		}
		while(tp>1){
			add(g,st[tp-1],st[tp]);
			--tp;
		}
		dfs1(st[1]);
		dfs2(st[1],nr[st[1]].first,nr[st[1]].second);
		dfs3(st[1]);
		dfs4(st[1]);
		ans[hr[st[1]]]+=sz[1]-sz[st[1]];
		for(int i=1;i<=m;++i){
			printf("%d ",ans[ppt[i]]);
		}
		puts("");
		dfs5(st[1]);
		for(int i=1;i<=m;++i){
			ans[pt[i]]=0,usd[pt[i]]=0;
		}
	}
}
int main(){
	init();
	return 0;
}

lp4582 FJOI2014 树的重心

两个重心的情况想想都麻。我们首先考虑一个重心的情况。 我们把 假设我们现在已经求出了每个子树的大小,那么我们发现,一棵子树有且仅有它的大小是对答案有影响的。所以我们可以预处理出每棵子树的不同大小的联通结构数,然后枚举子树大小瞎统计一下。 那么想想要怎么预处理。我们令\(f_{i,j}\)表示以\(i\)为根节点的子树中选取\(j\)个节点的联通子树的个数,\(g_{i,j}\)表示当前子树前\(i\)个儿子选取\(j\)个的联通子树的个数。 那么,根据定义我们有: $$g_{nw,j}=\sum_{k=1}^{j}g_{nw-1,k}f_{v,j-k}$$ $$f_{X,i}=g_{sum\_of\_sons,i-1}$$ 然后树形DP即可。 仔细想想,如果有两个重心,那么把两个重心的连边断开,两边的答案的统计是互不干扰的。 故而我们可以将原树分成两棵树统计答案,再把答案相乘。

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

const int MOD=10007;
const int INF=0x3f3f3f3f;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[404];
int h[205],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 sz[205],mx[205],rt=0,rt2=0,totsz,Tid=0,n;
inline void dfs0(int X,int FA){
	sz[X]=1;mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA){
			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],totsz-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
		rt2=0;
	}else if(mx[X]==mx[rt]){
		rt2=X;
	}
}
int f[205][205],g[205][205];
inline void dfs1(int X,int FA){
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs1(e[i].v,X);
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n;++j){
			g[i][j]=0;
		}
	}
	f[X][1]=f[X][0]=g[0][0]=sz[X]=1;
	int nw=1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		sz[X]+=sz[e[i].v];
		for(int j=0;j<=sz[X];++j){
			for(int k=0;k<=j;++k){
				g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[i].v][k]%MOD)%MOD;
			}
		}
		++nw;
	}
	--nw;
	for(int i=1;i<=sz[X];++i){
		f[X][i]=g[nw][i-1];
	}
}
int ans=0;
inline void calc1(){
	ans=1;
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,0);
	for(int i=2;i<=n;++i){
		for(int j=0;j<=n;++j){
			for(int k=0;k<=n;++k){
				g[j][k]=0;
			}
		}
		g[0][0]=1;int nw=1;sz[rt]=1;
		Fv(E,rt){
			sz[rt]+=sz[e[E].v];
			for(int j=0;j<=Min(i-1,sz[rt]);++j){
				for(int k=0;k<=j;++k){
					if(2*k>=i){
						break;
					}
					g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[E].v][k]%MOD)%MOD;
				}
			}
			++nw;
		}
		--nw;
		ans=(ans+g[nw][i-1])%MOD;
	}
}
inline void calc2(){
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,rt2);dfs1(rt2,rt);
	ans=0;
	for(int i=1;i<=n/2;++i){
		ans=(ans+f[rt][i]*f[rt2][i]%MOD)%MOD;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	et=rt=rt2=0;
	for(int i=1;i<=n;++i){
		h[i]=sz[i]=0;
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	totsz=n;
	mx[0]=INF;
	dfs0(1,0);
	if(!rt2){
		calc1();
	}else{
		calc2();
	}
	printf("Case %d: %d\n",Tid,ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		++Tid;
		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;
}

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;
}

lp1131 ZJOI2007 时态同步

有一棵树,每次将一条边的长度增加1的代价为1,求,使得所有叶节点到根节点距离相同的最小代价。
很显然,对于一棵树来说,贪心地考虑,最终的距离显然是最开始的最远叶节点的距离。
然后,继续贪心地考虑,每一次增加的代价,应当避免那些已经是最远距离的节点。
但是这样做的话复杂度最坏是n^2的。
故而我们考虑树形DP。对于每个节点临时记以这个节点为根的子树完成时态同步需要的代价。然后每一次修改把修改结果记下来即可。

#include<iostream>
#include<cstdio>

inline int Max(int A,int B){
	return A>B?A:B;
}
struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[500005],et=0;
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
int n,s,f[500005];
long long ans=0;
inline void dfs(int X,int FA){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs(e[i].v,X);
	}
	int mx=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		mx=Max(mx,f[e[i].v]+e[i].w);
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		ans+=mx-(f[e[i].v]+e[i].w);
	}
	f[X]=mx;
}
void init(){
	scanf("%d%d",&n,&s);
	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(s,0);
	printf("%lld\n",ans);
}

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

NOIP2018 赛道修建

一道树形DP裸题。
因为部分分给得很足,所以我在考场上先打了一堆部分分,建了5个命名空间。
然后在打二叉树的部分分的时候想到了正解。(虽然可能二分写挂了)
题目大意:给定一棵带权树,将它的一部分拆成\(m\)条链,使得权值最短的链的权值最大。
最小的求最大,当然满足无后效性,所以我们考虑二分答案。
然后我们考虑检验。首先,很容易可以发现答案具有无后效性。换句话说,每个子树在计算出它对答案的贡献之后,就只需要计算出它对父节点的贡献。
这是因为,每一个父节点,它能使用的仅有子树的一条链,而不是整个子树的信息。
故而,我们只需要「可以提供给父节点的那条链」的值更新上去即可。我们用\(f_{x}\)表达这个上传的值。
并且,对于每棵子树是可以贪心地处理的——如果一棵子树中的一条链可以和另一条链组成一条合法的链,那就没必要把它上传了。
这是因为,如果不上传,一定可以对答案产生1的贡献;如果上传了,仅仅是有可能对答案产生1的贡献。
那么我们对每个子树分别考虑。这就转化为了一个新的问题:
「对于一个长度为\(n\)的序列,取出其中尽可能多的数对或数,使得数对的和或数的值大于给定值,并且在有遗留数的情况下使得遗留的数的值最大。」
这个问题要怎么做呢?将它们从小到大排序,那么对于大于给定值的数,单独选取是更优的。
然后处理剩下来的数。用双指针做。
如果右指针的数可以与左指针指的数组成合法数对就把右指针推入栈中,直到没有合法的右指针,就考虑栈中是否为空。
如果不为空就说明存在一个可以和左指针匹配的数,那么就将答案加一,否则左指针就找不到数和它匹配了,那么就用它来更新\(f{x}\)左指针往右推。一直到序列为空。
然后,对于剩下的数,它们一定都可以组成合法数对——这是因为所有被推入栈中的数,都可以和一个比栈中最小数还要小的数组成合法数对。
那么,我们考虑剩下的数的数量的奇偶性。如果是奇数个,那么就计算答案之后用最大值来更新\(f_{x}\)。
这就做完了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
struct ee{
	int v;
	int w;
	int nxt;
}e[50005];
int h[50005],et=0;
int n,m;
inline void add(int u,int v,int w){
	e[++et]=(ee){v,w,h[u]};
	h[u]=et;
}
int MN,rt=0,f[50005],nw;
int st[50005],tp=0,st2[50005],tp2=0;
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
	}
	tp=0,tp2=0;
	for(int i=h[X];i;i=e[i].nxt){
		st[++tp]=f[e[i].v]+e[i].w;
	}
	std::sort(st+1,st+1+tp);
	while(tp&&st[tp]>=MN){
		--tp;
		++rt;
	}
	for(int i=1;i<=tp;++i){
		while(i<tp&&st[i]+st[tp]>=MN){
			st2[++tp2]=st[tp];
			--tp;
		}
		if(tp2){
			--tp2;
			++rt;
		}else{
			f[X]=st[i];
		}
	} 
	if(tp2&1){
		f[X]=st2[1];
	}
	rt+=(tp2>>1);
} 
inline bool chck(int X){
	std::memset(f,0,sizeof(f));
	MN=X;
	rt=0;
	dfs(1);
	if(rt>=m){
		return 1;
	}else{
		return 0;
	}
}
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);
		if(u>v){
			u^=v^=u^=v;
		}
		add(u,v,w);
	}
	int l=0,r=0x3f3f3f3f,mid,ans=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(chck(mid)){
			l=mid+1;
			ans=mid;
		}else{
			r=mid-1;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}