• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

树的直径

开发技术 开发技术 6小时前 1次浏览

树形DP

int f[N],mx;	//子树最长链
void dfs(int u,int fa)
{
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v;
		if(v == fa) continue;
		dfs(v,u);
		mx = max(mx,f[u] + f[v] + e[i].w);
		f[u] = max(f[u],f[v] + e[i].w);
	}
}

2遍DFS

先以任意节点为根,dfs找出最远的点,再以这个点为根 dfs 找出最远的点,这两个点即为直径的连个端点。

(代码找不到了,又懒得写。。。)

程序员灯塔
转载请注明原文链接:树的直径
喜欢 (0)