LG4381 [IOI2008] Island
给定一个基环树森林，求每棵基环树的直径长度和。直径是基环树上最长的一条简单路径。题目保证树边的方向构成了一颗内向树。
题解
先简单说一下为什么是一颗内向树，因为题目是给每个点一个与之相邻的点，即点对 \((u,v)\)，而且不会出现 \((v,u)\)。首先 \(n\) 个点 \(n\) 条边是一个基环树（森林），其次环上的点一定是互相指的，不然不能成环，然后环外的点一定是指向环的方向的，不然树不能联通。
把基环树拆成多个树，每个环上的点都是一颗树的树根，对这些树分别求其直径和到根最远的点的距离。这个过程可以树形 DP 得到。定义 \(f_i\) 为 \(i\) 到其子树内最深点的距离，\(g_i\) 为 \(i\) 子树的直径。
\[f_u\gets f_v+w\\ g_u\gets \max\{f_u+f_v+w,g_v\} \]然后我们考虑环上两个点 \(u,v\) 怎么组合，断环为链，定义 \(dis(u,v)\) 为链上两点的距离，\(sum\) 为链长，那么答案即为
\[\max\{f_u+f_v+dis(u,v),f_u+f_v+sum-dis(u,v),g_u,g_v\} \]直接这样计算是 \(O(n^2)\) 的。
我们可以随机找一个点作为链的起点断开，然后顺着扫环，不断更新 \(sum\)（即一个可以不存下来的前缀和）。
维护 \(maxv1=\max f_u-sum_{u-1}\) 和 \(maxv2=\max f_u+sum_{u-1}\)。
假如一个新点 \(v\) 的时候，显然 \(f_v+maxv_1+sum_v=f_u+f_v+sum_v-sum_{u-1}=f_u+f_v+dis(u,v)\)，就是答案的一部分。
同样 \(f_v+maxv_2-sum_v=f_u+f_v-(sum_v-sum_{u-1})=f_u+f_v-dis(u,v)\)，这个答案最后加上 \(sum\) 也是答案的一部分。
这样我们就可以 \(O(n)\) 地统计答案了。
实现
可以使用拓扑排序，入度为 \(0\) 的点就是叶子节点，从叶子节点晚上做树形 DP，显然环上的点在执行完拓扑之后入度均为 \(1\)，然后就看可以愉快的进行上面的过程了，其他细节见代码。
const int N=1000006;
const ll INF=0x3f3f3f3f3f3f3f3f;//ans2必须赋值成-INF!
int n,tar[N],wei[N],ind[N];
ll f[N],g[N];
queue<int>q;
inline ll solve(int u){
int sen=u;
ll ans1=g[u],ans2=-INF,maxv1=f[u],maxv2=f[u];
ll sum=wei[u];ind[u]=0,u=tar[u];
while(u!=sen){
ans1=max(ans1,g[u]);
ans1=max(ans1,f[u]+sum+maxv1);
ans2=max(ans2,f[u]-sum+maxv2);
maxv1=max(maxv1,f[u]-sum);
maxv2=max(maxv2,f[u]+sum);
sum+=wei[u];ind[u]=0;u=tar[u];
}
return max(ans1,ans2+sum);
}
int main(){
n=read();
for(int i=1;i<=n;++i){
tar[i]=read(),wei[i]=read();
++ind[tar[i]];
}
for(int i=1;i<=n;++i)
if(!ind[i])q.push(i);
while(!q.empty()){
int u=q.front(),v=tar[u],w=wei[u];q.pop();
ll dis=f[u]+w;
g[v]=max(max(g[v],g[u]),f[v]+dis);
f[v]=max(f[v],dis);
if(!--ind[v])q.push(v);
}
ll ans=0;
for(int i=1;i<=n;++i)
if(ind[i])ans+=solve(i);
printf("%lld\n",ans);
return 0;
}
大概是人生中的第一道基环树题？（不是
标签：IOI2008,Island,int,题解,sum,ans1,max,ll,dis From： https://www.cnblogs.com/BigSmall-En/p/16744784.html