题意
求基环树森林所有基环树的直径之和
题解
考虑的一个基环树的直径,只会有两种情况,第一种是某个环上结点子树的直径,第二种是从两个环上结点子树内的最深路径,加上环上这两个结点之间的较长路径。
那就找环,然后环上每个结点做树形\(dp\)。然后把环断成长度为\(2n\)的链,记录环上的前缀和\(sum\)。假设结点\(u\)子树内最深路径为\(dep[u]\),那么就是求\(max(sum[i] - sum[j] + dep[i] + dep[j]),j < i\)。这个就转换成\(max(sum[i] + dep[i] + dep[j] - sum[j])\),用单调队列维护最大的\(dep[j] - sum[j]\)就行,类似滑动窗口。
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
struct Edge {
int v, nxt, w;
} e[N << 1];
int hd[N], edge_num;
void link(int u, int v, int w) {
e[edge_num] = (Edge) {v, hd[u], w};
hd[u] = edge_num ++;
}
int n, loop[N], cnt, idx, dfn[N];
int fa[N], faw[N], loopw[N];
ll dep1[N], dep2[N], tree_d;
ll sum[N << 1], dep[N << 1];
bool onloop[N];
deque<int> q;
void dfs(int u, int cur = -1) {
dfn[u] = ++ idx;
for(int i = hd[u]; ~ i; i = e[i].nxt) {
if(cur == i) continue ;
int v = e[i].v;
if(dfn[v]) {
if(dfn[v] > dfn[u] || cnt) continue ;
cnt ++;
loop[cnt] = u;
loopw[cnt] = e[i].w;
for(int j = u; j != v; j = fa[j]) {
cnt ++;
loop[cnt] = fa[j];
loopw[cnt] = faw[j];
}
} else fa[v] = u, faw[v] = e[i].w, dfs(v, i ^ 1);
}
}
void dp(int u, int f = 0) {
dep1[u] = dep2[u] = 0;
for(int i = hd[u]; ~ i; i = e[i].nxt) {
int v = e[i].v;
if(v == f || onloop[v]) continue ;
dp(v, u);
ll dis = e[i].w + dep1[v];
if(dis > dep1[u]) {
dep2[u] = dep1[u];
dep1[u] = dis;
} else if(dis > dep2[u]) {
dep2[u] = dis;
}
}
tree_d = max(tree_d, dep1[u] + dep2[u]);
}
int main() {
scanf("%d", &n);
fill(hd + 1, hd + n + 1, -1);
for(int i = 1, v, w; i <= n; i ++) {
scanf("%d%d", &v, &w);
link(v, i, w);
link(i, v, w);
}
ll ans = 0, d;
for(int i = 1; i <= n; i ++)
if(!dfn[i]) {
cnt = 0; dfs(i);
for(int j = 1; j <= cnt; j ++)
onloop[loop[j]] = 1;
d = 0;
for(int j = 1; j <= cnt; j ++) {
tree_d = 0;
dp(loop[j]);
dep[j] = dep[j + cnt] = dep1[loop[j]];
d = max(d, tree_d);
}
for(int j = 1; j <= cnt << 1; j ++)
sum[j] = sum[j - 1] + loopw[j <= cnt ? j : j - cnt];
q.clear();
for(int j = 1; j <= cnt << 1; j ++) {
//sum_j + dep_j + dep_i - sum_i
for(; !q.empty() && q.front() + cnt - 1 < j; q.pop_front()) ;
ll c = dep[j] - sum[j];
if(!q.empty()) d = max(d, sum[j] + dep[j] + dep[q.front()] - sum[q.front()]);
for(; !q.empty() && dep[q.back()] - sum[q.back()] <= c; q.pop_back()) ;
q.push_back(j);
}
ans += d;
}
printf("%lld\n", ans);
return 0;
}
什么,\(\text{BZOJ}\)上\(10^6\)会爆栈?那只能手工栈了。。
「BZOJ 1791」「IOI 2008」Island「基环树」
原文:https://www.cnblogs.com/hongzy/p/10357432.html