这个图跟信息传递很像，也就是一个基环树，但是我很思博地没看出来。。。
事实上这是一个基环树森林，我们要求的是每棵基环树的直径（不太准确），也就是基环树上最长的路径
首先得找到环，这里我们可以分两种情况
1.这条路径在环上，那么也就是说两个端点在环上某个顶点的子树里或环上，那么这个样子可以这么计算：dis=d子树1+d子树2+d环，我们先把环拉开复制一遍接在后面，然后对于环上每个顶点的子树计算一下子树最深的地方到环上该点的距离，这些子树取个最大值。然后就可以dp了dp[i] = max(dp[i], d[i]-d[j]) 这里可以用单调队列优化，具体看代码
2.最长路径位于环上某个顶点的子树里，或者跨越某个顶点的两颗子树。这里就是一个树形dp，代码里写的不清楚，其实就是求树的直径的代码。
吐槽：写了4个小时，忽略了好几种情况，竟然还会爆栈，我不会写手工栈。。。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1000010; struct edge { int nxt, w, to; } e[N << 1]; vector<int> route; int n, cnt = 1, pos; ll ans, Max; int used[N], vis[N], head[N], mark[N], w[N], prev[N], pree[N << 1]; ll mx[N], d[N << 1], g[N], q[N], dp[N]; inline int read() { int x = 0, f = 1; char c = getchar(); while(c < ‘0‘ || c > ‘9‘) { if(c == ‘-‘) f = -1; c = getchar(); } while(c >= ‘0‘ && c <= ‘9‘) { x *= 10; x += c - ‘0‘; c = getchar(); } return x * f; } inline void link(int u, int v, int w) { e[++cnt].nxt = head[u]; head[u] = cnt; e[cnt].to = v; e[cnt].w = w; } void Dp(int u, int last) { ll Max1 = 0, Max2 = 0; for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last) { Dp(e[i].to, u); if(g[e[i].to] + (ll)e[i].w >= Max1) { Max2 = Max1; Max1 = g[e[i].to] + (ll)e[i].w; } else if(g[e[i].to] + (ll)e[i].w > Max2) Max2 = g[e[i].to] + (ll)e[i].w; Max = max(Max, Max1 + Max2); } g[u] = Max1; } bool getcir(int u, int last) { vis[u] = 1; bool flag = false; for(int i = head[u]; i; i = e[i].nxt) { if(e[i].to == last && !flag) { flag = true; continue; } if(!vis[e[i].to]) { prev[e[i].to] = u; pree[e[i].to] = i; if(getcir(e[i].to, u)) return true; } else { pree[e[i].to] = i; pos = u; prev[e[i].to] = u; return true; } } return false; } void dfs(int u) { used[u] = 1; for(int i = head[u]; i; i = e[i].nxt) if(!used[e[i].to]) dfs(e[i].to); } void solve(int u) { route.clear(); getcir(u, 0); for(int now = pos; !mark[now]; now = prev[now]) { mark[now] = 1; route.push_back(now); w[now] = e[pree[now]].w; } for(int i = 0; i < route.size(); ++i) { ll Max1 = 0, Max2 = 0; for(int j = head[route[i]]; j; j = e[j].nxt) if(!mark[e[j].to]) { Dp(e[j].to, route[i]); if(g[e[j].to] + (ll)e[j].w >= Max1) { Max2 = Max1; Max1 = g[e[j].to] + e[j].w; } else if(g[e[j].to] + e[j].w > Max2) Max2 = g[e[j].to] + e[j].w; mx[route[i]] = max(mx[route[i]], g[e[j].to] + (ll)e[j].w); dp[route[i]] = max(dp[route[i]], max(Max, Max1 + Max2)); Max = 0; } } int lim = route.size(), l = 0, r = 0; for(int i = 0; i < lim; ++i) route.push_back(route[i]); d[0] = q[l] = 0; for(int i = 0; i < route.size(); ++i) d[i + 1] = d[i] + w[route[i]]; ll delta = mx[route[0]] + d[0]; for(int i = 0; i < route.size(); ++i) { while(q[r] - q[l] + 1 >= lim && l <= r) ++l; if(i) delta = max(delta, mx[route[i]] + d[i] + mx[route[q[l]]] - d[q[l]]); delta = max(delta, dp[route[i]]); ll x = mx[route[i]] - d[i]; while(l <= r) if(x > mx[route[q[r]]] - d[q[r]]) --r; else break; q[++r] = i; } ans += delta; dfs(u); } int main() { // int size = 50 << 20; // 256MB // char *p = (char*)malloc(size) + size; // __asm__("movl %0, %%esp\n" :: "r"(p)); freopen("isl.in", "r", stdin); freopen("isl.out", "w", stdout); n = read(); for(int i = 1; i <= n; ++i) { int u, w; u = read(); w = read(); link(i, u, w); link(u, i, w); } for(int i = 1; i <= n; ++i) if(!used[i]) solve(i); printf("%lld\n", ans); fclose(stdin); fclose(stdout); return 0; }
原文：http://www.cnblogs.com/19992147orz/p/6660007.html