树的直径可能不是唯一的，但树的中点是唯一的，我的意思是..
有以下两种办法求得树的直径：
- 两遍 DFS（或BFS）：可以记录点
- 树形 DP：允许有负边权
首先是 两遍 DFS 可求路径
点击查看代码
int head[N], cnt;
struct Edge {
int from, to, nxt;
ll val;
}e[N << 1];
void add(int u, int v, ll val){
e[++cnt].from = u;
e[cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
e[cnt].val = val;
}
ll dis[N], fa[N];
void dfs(int u, int father, ll d){
fa[u] = father;
dis[u] = d;
for(int i = head[u]; i != 0; i = e[i].nxt){
int v = e[i].to;
if(v == father) continue;
dfs(v, u, d + e[i].val);
}
}
ll max_len(int &beg, int &ed){
dfs(1, -1, 0);
beg = 1;
for(int i = 1; i <= n; i++){
if(dis[i] > dis[beg]) beg = i;
}
dfs(beg, -1, 0);
for(int i = 1; i <= n; i++){
if(dis[i] > dis[ed]) ed = i;
}
return dis[ed];
}
然后是 树形DP 做法，可以维护负边权
点击查看代码
int head[N], cnt;
struct Edge {
int from, to, nxt;
ll val;
}e[N << 1];
void add(int u, int v, ll val){
e[++cnt].from = u;
e[cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
e[cnt].val = val;
}
ll dp[N], maxlen;
bool vis[N];
void dfs(int u){
vis[u] = true;
for(int i = head[u]; i != 0; i = e[i].nxt){
int v = e[i].to;
if(vis[v]) continue;
dfs(v);
maxlen = max(maxlen, dp[u] + dp[v] + e[i].val);
dp[u] = max(dp[u], dp[v] + e[i].val);
}
return ;
}