图论（树的直径）

一、基础

树中最远的两个结点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链（也称直径）

二、两次遍历求直径

1、从任意一个结点出发，通过bfs或者dfs对树进行一次遍历，求出与出发点距离最远的结点，记为p，这就是树的直径的一端

2、从结点p出发，通过bfs和dfs对树再进行一次遍历，求出与p距离最远的结点，记为q

3、那么p到q的路径就是树的一条直径，因为p一定是直径的一端，否则总能找到一条更长的链。在第二步遍历过程中，可以记录下来每个点第一次被访问时的前驱节点，最后从q回溯到p即可得到直径的具体方案

4、注：通过搜索不能解决负边权的问题

int to[maxn << 1], nex[maxn << 1], edge[maxn << 1], head[maxn];
int cnt, n, m, r;
ll  dis[maxn], maxd, maxv;
void add(int u, int v, int w)
{
	to[++cnt] = v;
	edge[cnt] = w;
	nex[cnt] = head[u];
	head[u] = cnt;
}
void dfs(int u, int fa)
{
	if (maxd < dis[u])
	{
		maxd = dis[u];
		maxv = u;
	}
	for (int i = head[u]; i; i = nex[i])
	{
		int v = to[i];
		if (fa == v)
			continue;
		dis[v] = dis[u] + edge[i];
		dfs(v, u);
	}
}
void solve()
{
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	dfs(1, 0);
	maxd = 0;
	dis[maxv] = 0;
	dfs(maxv, 0);
	cout << maxd;
}

三、树形dp求直径

1、设d[x]表示从结点x出发走向以x为根的子树，能够到达的最远节点的距离，即x向下走的最长链，显然有

2、那么我们可以考虑求出经过每个点x的最长链的长度f[x]，那么整个树的直径就是最大的f[x]。对于x的任意两个结点yi，yj，经过结点x的最长链的长度由四部分组成，如下

3、当子节点枚举到i时，d[x]正好保存了从x出发向以yi为根的子树能达到的最远的结点的距离，这个距离就是，所以我们先用更新f[x]，再用更新d[x]即可

int to[maxn << 1], nex[maxn << 1], edge[maxn << 1], head[maxn];
int vis[maxn];
int cnt, n, m, r;
ll ans = 0, d[maxn];
void add(int u, int v, int w)
{
	to[++cnt] = v;
	edge[cnt] = w;
	nex[cnt] = head[u];
	head[u] = cnt;
}
void dp(int u)
{
	vis[u] = 1;
	for (int i = head[u]; i; i = nex[i])
	{
		int v = to[i];
		if (vis[v])
			continue;
		dp(v);
		ans = max(ans, d[u] + d[v] + edge[i]);
		d[u] = max(d[u], d[v] + edge[i]);
	}
}
void solve()
{
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	dp(1);
	cout << ans << '\n';
}