[模板] 基础树上动规

树的直径

  • 方法一 : 两次dfs

  • 方法二 : 利用动规求解,以每个结点向下延伸的最长长度为状态,顺便记录下向下延伸的次长长度,则数的直径便为 d1 + d2。

void dfs(int x,int fa){
	f[x] = 1;
	int mx = 0;
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y==fa) continue;
		dfs(y,x);
		f[x] = max(f[x], f[y]+1);
		ans = max(ans, mx+f[y]+1);
		mx = max(mx, f[y]);
	}
	ans = max(ans, f[x]);
}

这里有一个小细节,上面代码求的是点直径,就是直径包含多少个点,如果我们计算边的个数,我们只需要把f[ x ]初始化改为1,令ans=max(ans,mx+f[ y ]+2)。

树的重心

void dfs(int x,int fa){
	siz[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y==fa) continue;
		dfs(y,x);
		siz[x] += siz[y];
		mx[x] = max(mx[x], siz[y]);
	}
	mx[x] = max(mx[x], n-siz[x]);
}

最后再找到mx[ x ]最小的下标即是答案

上一篇:kurbenetes中的informer使用方法


下一篇:luogu P5043 【模板】树同构([BJOI2015]树的同构)