「POJ1985」Cow Marathon

题意：求一个 $n$ 个点的树中树的直径。

树的直径模板题。

---

性质

1.直径两端点一定是叶子节点。

2.距任意点最远点一定是直径的端点，据所有点最大值最小的点一定是直径的中点。

3.两棵树相连，新直径的两端点一定是原四个端点中的两个。

4.两棵树相连，设 $l$ 为树的直径长度，$q$ 为树的半径长度，$w$ 为两棵树相连的边的长度，$k$ 为直径中最接近中点的节点，新直径长度最小为 $max(max(l _1,l _2),q _1+q _2+w)\ (q=max(tot-d[k],d[k]))$。

5.一棵树上接一个叶子结点，直径最多改变一个端点。

6.若一棵树存在多条直径，多条直径交于一点，且交点是直径的严格中点(中点可能在某条边内)。

方法

树形 DP

用 $d[x]$ 代表从点 $x$ 出发，能到达的最远的点的路径长度，那么如果对于任意一个 $x$ 的儿子 $y$，满足以下关系式：

$$d[x]=\max _{father[y]=x} (d[y]+w(x,y))$$

设 $ans$ 即为树的直径的长度，那么对于每一个点 $x$，在以 $
$x$ 为根的子树中，设 $y_i$ 和 $y_j$ 是 $x$ 的儿子，那么

$$ans=\max _{father[y _i,y _j]=x} (dis[y _i]+w(y _i,x)+w(x,y _j)+dis[y _j])$$

如果我们每次遍历时都遍历 $y _i$ 和 $y _j$ ，那么时间复杂度会高很多，由于我们在每次求 $ans$ 时，$d[x]$ 在上次递归中正好保存其中一个子节点，所以我们在求 $ans$ 时，可以直接使用 $d[x]$，如下：

$$ans=\max _{father[y]=x} (d[x]+d[y]+w(x,y))$$

code:

void dp(int u,int fa)
{
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		dp(v,u);
		ans=max(ans,d[u]+d[v]+e[i].num);
		d[u]=max(d[u],d[v]+e[i].num);
	}
}

优点：树形 DP 方便，代码量小，且效率较高，支持负权边。

缺点：只能求长度，不能记录路径和两端点。

两次 DFS (BFS)

由树的直径的最长性可知，我们可以现在树中随便找一个节点，然后 $dfs$ 到所能到达的最远端点，这个端点必然是直径的一端，然后我们再从这个端点出发，再次 $dfs$ 到所能到达的最远端点，这两个端点之间的路径就是直径。

void dfs(int u,int fa)
{
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		dis[v]=dis[u]+e[i].num;
		if(dis[v]>ans)
		{
			ans=dis[v];//dfs过程中不断更新直径最大值
			rt=v;
		}
		dfs(v,u);
	}
	return ;
}
int main()
{
    //...省略输入，建图等过程
	dfs(1,0);//从一个端点出发
	ans=0;
	int p=rt;//p为直径一端点
	memset(dis,0,sizeof(dis));
	dfs(p,0);//再次dfs
	printf("%d",dis[rt]);//直径长度
}

优点：多变，可记录端点和路径。

缺点：不支持负权边，时间复杂度较高。

---

这道题的代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int dis[501010],ans,rt;
int head[501010],cnt;
struct node
{
	int next;
	int to;
	int num;
}e[1010101];
void add(int from,int to,int num)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	e[cnt].num=num;
	head[from]=cnt;
}
void dfs(int u,int fa)
{
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		dis[v]=dis[u]+e[i].num;
		if(dis[v]>ans)
		{
			ans=dis[v];
			rt=v;
		}
		dfs(v,u);
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		char s;
		scanf("%d%d%d %c",&a,&b,&c,&s);
		add(a,b,c);
		add(b,a,c);
	}
	dfs(1,0);
	ans=0;
	int p=rt;
	memset(dis,0,sizeof(dis));
	dfs(p,0);
	printf("%d",dis[rt]);
	return 0;
}