题解
题意 = 找出无向基环树森林的每颗基环树的直径。
我们首先需要找到每颗基环树的环， 但是因为是无向图，用tarjan找环， 加个手工栈， 我也是看了dalao的博客才知道tarjan找无向图环 ：
然鹅大佬的方法有一点小问题， 无法找出只有两个节点的环，改动后代码：
void dfs(int x, int last) {
dfn[x] = ++sz;
for(int i = head[x]; i; i = e[i].nxt) {
if(i == last ^ ) continue;
int nt = e[i].to;
if(dfn[nt]) {
if(dfn[nt] < dfn[x]) continue;
cur.push_back(x); mk[x] = ;
for(; nt != x; nt = pre[nt]) cur.push_back(nt), mk[nt] = ;
}
else pre[nt] = x, dfs(nt, i);
}
}
加了手工栈后的代码
int lev2; int st_i2[N],st_x2[N],st_y2[N],st_t2[N]; #define i st_i2[lev2]
#define y st_y2[lev2]
#define x st_x2[lev2]
#define nt st_t2[lev2] void dfs(int u, int last) {
lev2 = ;
st_x2[] = u; st_y2[] = last;
start:;
dfn[x] = ++sz;
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
if(i == ch(y)) continue;
if(dfn[nt]) {
if(dfn[nt] < dfn[x]) continue;
cur.push_back(x); mk[x] = ;
for(; nt != x; nt = pre[nt]) mk[nt] = , cur.push_back(nt);
continue;
}
pre[nt] = x;
st_x2[lev2 + ] = nt;
st_y2[lev2 + ] = i;
lev2++;
goto start;
end:;
}
lev2--;
if(lev2) goto end;
} #undef i
#undef y
#undef x
#undef nt
设tmp 为某棵基环树的直径
tmp可能是某个环上点的子树的直径， 也有可能是环上两个点之间的距离+两个点到子树的最大距离
找出环后， 求出环上的每个点的子树中的直径， 每颗子树的直径中都更新 tmp的最大值。
接着求出从环上每个点到它子树节点的最远距离$d$， tmp的最大值也可能为 $d_i + d_j + dist(i, j)$。
这个式子最大值可以用拆环+单调队列O(N)求出。
然后把tmp 加到最后答案
代码
为什么不加手工栈比加了手工栈慢20倍
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#define rd read()
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define per(i,a,b) for(int i = (a); i >= (b); --i)
#define ll long long
#define R register
using namespace std; const int N = 1e6 + 1e5; int n, head[N], tot, dfn[N], pre[N], sz;
int q[N], mk[N], pos[N];
ll ans, d[N], f[N]; vector<int> pt;
vector<ll> len; struct edge {
int nxt, to, val;
}e[N << ]; int read() {
R int X = , p = ; R char c = getchar();
for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} void add(int u, int v, int val) {
e[++tot].to = v;
e[tot].val = val;
e[tot].nxt = head[u];
head[u] = tot;
} int ch(int x) {
return ((x + ) ^ ) - ;
} int lev2; int st_i2[N],st_x2[N],st_y2[N],st_t2[N]; #define i st_i2[lev2]
#define y st_y2[lev2]
#define x st_x2[lev2]
#define nt st_t2[lev2] void dfs(int u, int last) {
lev2 = ;
st_x2[] = u; st_y2[] = last;
start:;
dfn[x] = ++sz;
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
if(i == ch(y)) continue;
if(dfn[nt]) {
if(dfn[nt] < dfn[x]) continue;
pt.push_back(x); mk[x] = ;
for(; nt != x; nt = pre[nt]) mk[nt] = , pt.push_back(nt);
continue;
}
pre[nt] = x;
st_x2[lev2 + ] = nt;
st_y2[lev2 + ] = i;
lev2++;
goto start;
end:;
}
lev2--;
if(lev2) goto end;
} #undef i
#undef y
#undef x
#undef nt int lev;
int st_x[N], st_y[N], st_i[N], st_t[N]; #define i st_i[lev]
#define x st_x[lev]
#define y st_y[lev]
#define nt st_t[lev] void dfs2(int u, int fa) {
lev = ;
st_x[] = u; st_y[] = fa;
start:;
for(i = head[x]; i; i = e[i].nxt) {
nt = e[i].to;
if(nt == y || mk[nt]) continue;
st_x[lev + ] = nt;
st_y[lev + ] = x;
lev++;
goto start;
end:;
f[x] = max(f[x], f[nt]);
f[x] = max(f[x], d[x] + d[nt] + e[i].val);
d[x] = max(d[x], d[nt] + e[i].val);
}
lev--;
if(lev) goto end;
} #undef i
#undef x
#undef y
#undef nt void work(int x) {
ll tmp = ; int cnt;
pt.clear(); len.clear();
dfs(x, ); cnt = pt.size();
pt.push_back(pt[]);
len.push_back();
for(R int i = ; i < cnt; ++i) {
for(R int k = head[pt[i]]; k; k = e[k].nxt) if(e[k].to == pt[(i + ) % cnt])
len.push_back(e[k].val);
}
for(R int i = ; i < cnt; ++i)
pt.push_back(pt[i]), len.push_back(len[i]); rep(i, , cnt * - ) {
len[i] += len[i - ];
}
rep(i, , cnt - ) dfs2(pt[i], ), tmp = max(tmp, f[pt[i]]);
int l = , r = ;
rep(i, , cnt * - ) {
while(l <= r && i - q[l] >= cnt) l++;
if(l <= r) tmp = max(tmp, d[pt[i]] + d[pt[q[l]]] + len[i] - len[q[l]]);
else tmp = max(tmp, d[pt[i]]);
while(l <= r && d[pt[i]] - len[i] >= d[pt[q[r]]] - len[q[r]]) r--;
q[++r] = i;
}
ans += tmp;
} int main()
{
n = rd;
rep(i, , n) {
int v = rd, val = rd;
add(i, v, val); add(v, i, val);
}
rep(i, , n) if(!dfn[i]) {
work(i);
}
printf("%lld\n", ans);
}