题目大意
求各个基环树的直径和
先用dfs或拓扑排序找到基环树的环,把环上的点标记,再对每个点进行dfs,就可以访问以该点为根的子树。
在每棵子树中求出直径。设$f[x]$表示以$x$为根的子树的直径。设$i,j$为环上两点,$d[i]$表示环上边权的前缀和。
那么基环树的直径就是$f[i]+f[j]+d[j]-d[i]$,其中$d[j]-d[i]$是$i,j$两点的在环上的距离。对于d数组,可以把环断开复制一遍,枚举j,用单调队列维护$f[i]-d[i]$的最大值.
时间复杂度:$O(n)$
#include <iostream>
#include <queue>
using namespace std;
int n;
int nx[2000006],he[1000006],vr[2000006],eg[2000006],tot;
inline void add(int x,int y,int z){
vr[++tot]=y;
eg[tot]=z;
nx[tot]=he[x];
he[x]=tot;
}
int in[1000006],ku[1000006],v[1000006],t,q[2000006];
long long ans,d[1000006],f[1000006],a[1000006],b[1000006];
// 一定要开long long !!!
void topsort(){
queue<int> q;
for(int i=1;i<=n;++i) if(in[i]==1) q.push(i);
while(q.size()){
int x=q.front();
q.pop();
for(int i=he[x];i;i=nx[i]){
if(in[vr[i]]>1){
d[ku[x]]=max(d[ku[x]],f[x]+f[vr[i]]+eg[i]);
f[vr[i]]=max(f[vr[i]],f[x]+eg[i]);// 树的直径
if(--in[vr[i]]==1) {
q.push(vr[i]);
}
}
}
}
}
void dp(int k,int x){
int m=0;// 环上点的数量
int y=x,z=0,len=0;
do{
a[++m]=f[y];// 记录以环上各点为根的子树的直径
in[y]=1;
for(z=he[y];z;z=nx[z]){
if(in[vr[z]]>1){
y=vr[z];
b[m+1]=b[m]+eg[z];// 标记环上的点
break;
}
}
}while(z);
if(m==2){
for(int i=he[y];i;i=nx[i]){
if(vr[i]==x){
len=max(len,eg[i]);
}
}
d[k]=max(d[k],f[x]+f[y]+len);
return;
}
for(int i=he[y];i;i=nx[i]){
if(vr[i]==x){
b[m+1]=b[m]+eg[i];
break;
}
}
for(int i=1;i<m;++i){
a[i+m]=a[i];b[i+m]=b[m+1]+b[i]; // 复制
}
int l,r;
q[l=r=1]=1;// 单调队列
for(int i=2;i<(m<<1);++i){
while(l<=r && i-q[l]>=m) ++l;
d[k]=max(d[k],a[q[l]]+a[i]+b[i]-b[q[l]]);
while(l<=r && a[q[r]]-b[q[r]]<=a[i]-b[i]) --r;
q[++r]=i;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int x,z;
for(int i=1;i<=n;++i){
cin>>x>>z;
add(x,i,z);
add(i,x,z);
++in[x];++in[i];
}
queue<int> q;
for(int i=1;i<=n;++i){ // 遍历每个连通块
if(ku[i]) continue;
while(q.size()) q.pop();
q.push(i);
ku[i]=++t;
while(q.size()){
x=q.front();
q.pop();
for(int i=he[x];i;i=nx[i]){
if(ku[vr[i]]) continue;
q.push(vr[i]);
ku[vr[i]]=t;
}
}
}
topsort();// 拓扑排序
for(int i=1;i<=n;++i){
if(in[i]>1 && !v[ku[i]]) { // 如果该点入度大于1,那么就是环上的点
v[ku[i]]=1;// 标记
dp(ku[i],i);
ans+=d[ku[i]];// 统计每个基环树最长简单路径
}
}
cout<<ans;
return 0;
}
是数据加强了吗……好像T掉了……