【图论】树的直径

树的直径即为一棵树中距离最远的两点之间的路径

方法一：DFS

先以任意一点为起点跑一遍dfs，记录离起点距离最远的点p（这个点一定是直径的一个端点，感性理解一下不证明了），然后再以最远点再跑一遍dfs，记录此时距离最远的点q，那么pq就是该树的直接

树中有负权边时不可以用这个方法

const int N = 10000 + 10;int n, c, d[N];
vector<int> g[N];void dfs(int u, int fa)
{for (int v : E[u]){if (v == fa) continue;d[v] = d[u] + 1; // 如边有权值，把1换成权值即可if (d[v] > d[c]) c = v; // 更新最大距离的点dfs(v, u);}
}int main()
{cin >> n;for (int i = 1; i < n; i++){int u, v;scanf("%d %d", &u, &v);g[u].push_back(v), g[v].push_back(u);}dfs(1, 0); // 第一遍dfsint p = c; // 一个端点d[c] = 0;dfs(c, 0); // 第二遍dfsint q = c; // 另一个端点cout << d[c];return 0;
}

方法二：树形dp

dp[u]为以u为根的子树中离u最远的点的路径长度
转移方程（v为u的子结点）：dp[u] = max(dp[u], dp[v] + w(u, v))
两条经过根结点的最长路径即为该子树中的直径
转移方程：zj = max(zj, dp[u] + dp[v] + w(u, v))

const int N = 10000 + 10;int n, zj = 0;
int dp[N];
vector<int> g[N];void dfs(int u, int fa)
{for (int v : E[u]){if (v == fa) continue;dfs(v, u);zj = max(zj, dp[u] + dp[v] + 1); // 如为有权边，把1换成权值即可dp[u] = max(dp[u], dp[v] + 1); // 如为有权边，把1换成权值即可}
}int main()
{cin >> n;for (int i = 1; i < n; i++){int u, v;cin >> u >> v;g[u].push_back(v), g[v].push_back(u);}dfs(1, 0);cout << zj << '\n';return 0;
}