BZOJ 1791
题意：求基环森林中的每棵基环树的直径之和。
可以对每个基环树进行求解，显然答案为每个基环树直径的和。
考虑怎么求基环树的直径。
我们可以将环找出来，然后当成一个广义根，对环上每个点向下做树直径DP，然后问题转化为在一个环上选取两个数使得
$$
a(x)+a(y)+\max(|dis_x-dis_y|, dis_n - |dis_x-dis_y|)
$$
其中$dis_i$为从环上某个点某个方向出发到$i$的距离，$a$为每个点向下做的树直径长度。
注意到这个式子和CH 5501的式子类似，所以可以单调队列维护。具体方法和那题差不多。
找环的方法为dfs，同时记录时间戳，将当前搜索链(当前点到最祖先的节点的链)上的的加入到栈，若出现一条反向边，则一定存在一个环，并且这条边是环上的边，所以一直退栈直到取出反向边所指的节点。这些节点就是环上的点。但是注意了提前退出要把所有标记都标记好，否则有错解。
注意环上一个点有几个分支的情况，这必须在处理树直径时加上ans = max(ans, d[u] + d[e.v] + e.w)
单调队列中如果没有元素，则不能直接转移，只能更新为他的$a$值
fault1：提前退出没有把所有标记
fault2: 环上最优化错误
fault3：没有理解之前的题目(CH 5501)
fault4：单调队列没有元素时没有讨论
fault5: 基环树特殊数据
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 1000000 + 5;
struct edge {
int v, w, nxt;
} ed[MAXN * 2];
int n, hd[MAXN], en;
LL ans, finans, d[MAXN], ok[MAXN];
int dfn[MAXN], sz;
int vis[MAXN], cir[MAXN * 2], cnt_cir, fl, bq;
int stk[MAXN], top;
LL dis_cir[MAXN * 2];
int q[MAXN * 2], l, r;
void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}
LL abss(LL x) {return x > 0 ? x : -x;}
void dfs_graph(int u, int pre) { // fault1：提前退出没有把所有标记
if (fl) return ;
dfn[u] = ++sz, stk[++top] = u;
for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (fl) return ;
if (i != (pre ^ 1)) {
if (dfn[e.v]) {
if (fl) return ;
fl = 1;
int whw;
do {
whw = stk[top--];
vis[whw] = 1, cir[++cnt_cir] = whw;
} while (top && whw != e.v);
return ;
} else dfs_graph(e.v, i);
}
}
--top;
}
void dfs_cir(int ith) {
for (int i = hd[cir[ith]]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (ith == cnt_cir) {
if (e.v == cir[1]) {bq = e.w; return ;}
}
if (e.v == cir[ith + 1]) {
dis_cir[ith + 1] = dis_cir[ith] + e.w;
dfs_cir(ith + 1);
}
}
}
void dfs_tree(int u, int fa) {
ok[u] = 1;
for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (!vis[e.v] && e.v != fa) {
dfs_tree(e.v, u);
ans = max(ans, d[u] + d[e.v] + e.w);// fault5: 基环树特殊数据
d[u] = max(d[u], d[e.v] + e.w);
}
}
}
void clean() {
ms(hd, -1), en = -1, finans = 0, ms(ok, 0);
ms(dfn, 0), ms(d, 0), sz = 0ll;
}
int solve() {
clean();
scanf("%d", &n);
for (int v, w, u = 1; u <= n; ++u) {
scanf("%d%d", &v, &w);
ins(u, v, w), ins(v, u, w);
}
for (int u = 1; u <= n; ++u) if (!ok[u]) { // fault1：提前退出没有把所有标记
for (int i = 1; i <= cnt_cir; ++i) vis[cir[i]] = 0, dis_cir[i] = dis_cir[i + cnt_cir] = 0;
cnt_cir = 0ll, top = 0, ans = 0;
fl = 0;
dfs_graph(u, -1);
dfs_cir(1);
for (int i = 1; i <= cnt_cir; ++i) dfs_tree(cir[i], 0);
dis_cir[cnt_cir + 1] = dis_cir[cnt_cir] + bq;
for (int i = 2; i <= cnt_cir; ++i) dis_cir[cnt_cir + i] = dis_cir[cnt_cir + 1] + dis_cir[i];
for (int i = 1; i <= cnt_cir; ++i) cir[i + cnt_cir] = cir[i];
// fault2: 环上最优化错误
l = 1, r = 0;
for (int i = 1; i <= cnt_cir * 2; ++i) {
while (l <= r && i - q[l] >= cnt_cir) ++l; // fault3：没有理解之前的题目
if (l <= r) ans = max(ans, d[cir[i]] + dis_cir[i] + d[cir[q[l]]] - dis_cir[q[l]]); else ans = max(ans, d[cir[i]]); // fault4：单调队列没有元素时没有讨论
while (l <= r && d[cir[q[r]]] - dis_cir[q[r]] <= d[cir[i]] - dis_cir[i]) --r;
q[++r] = i;
}
finans += ans;
}
cout << finans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
6 7
1 2 1
2 3 3
2 4 4
4 5 5
4 6 2
3 5 6
5 6 2
*/
