基环树学习笔记
https://517coding.com/contests/2395/problem/A
这道题可以分为几个步骤来做
1.找环
我们可以直接用一个 dfs，搜到以前标记过的就说明是一个环并且不断回溯并记录环。
而通过样例，我们可以发现我们不能通过父节点判重，应该以是否是从原来的边经过来判定，而我们链式前向星中的 $idx$ 编号是连续的，所以可以以此来判定是否是原来的边。
然后如果能搜到以前搜过的就记录环并返回 $1$，接收到这个标记的点就记录环并不断回溯，一边回溯一边更新环的距离，$dis$ 数组表示环间距离。
2.处理环
因为只有一个环，所以环上的每个点肯定都是一棵树的根，可以找到以根节点为出发点在树上的最长路。
而我们发现，其实一棵基环树的最长路径其实就是某两个点在环上的距离加上这两个点分别在自己的树上的最长路。
于是，我们可以断环成链把环复制一份，把环的边权做一个前缀和，这样就能清楚地知道两点间的最长距离。
而算出最大的距离的式子应是 $dis_j-dis_i+mx_i+mx_j$，其中 $mx$ 表示树上最长路。我们发现这个式子可以分成 $dis_j+mx_j$ 和 $mx_i-dis_i$ 两部分，后者可以通过单调队列找得最大值，进行求 $mx$。
最后把每棵基环树的最大值输出。注意，基环树上的某棵树的直径也可能是答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| #include <bits/stdc++.h>
using namespace std;
const int N = 2000010;
long long h[N],e[N],ne[N],w[N],idx=1,mx[N];
int vis[N];
int c[N],ttt=0;;
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
bool flag[N];
long long ans=0,res=0;
void search(int u,int v)
{
long long mx2=0,mx1=0;
flag[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
if(e[i]!=v && !flag[e[i]])
{
search(e[i],u);
if(mx[e[i]]+w[i]>=mx1)
{
mx2=mx1,mx1=mx[e[i]]+w[i];
}
else if(mx[e[i]]+w[i]>=mx2) mx2=mx[e[i]]+w[i];
}
}
ans=max(ans,mx1+mx2);
mx[u]=mx1;
}
long long dis[N];
int q[N],t=0,f=1;
void solve()
{
long long mxx=0;
for(int i=1;i<=ttt;i++) flag[c[i]]=1;
long long qq=0;
for(int i=1;i<=ttt;i++)
{
c[i+ttt]=c[i];
dis[i+ttt]=dis[i+ttt-1]+dis[i]-dis[i-1];
}
for(int i=1;i<=ttt;i++)
{
search(c[i],c[i]);
qq=max(qq,ans);ans=0;
}
for(int i=ttt+1;i<=ttt<<1;i++) mx[c[i+ttt]]=mx[c[i]];
t=1;
q[t]=1;
for(int i=2;i<=ttt<<1;i++)
{
while(t>=f && q[f]<=i-ttt) f++;
mxx=max(mxx,dis[i]-dis[q[f]]+mx[c[q[f]]]+mx[c[i]]);
while(t>=f && mx[c[q[t]]]-dis[q[t]]<mx[c[i]]-dis[i]) t--;
t++;q[t]=i;
}
t=0,f=1;
res+=max(mxx,qq);
ttt=0;
}
int dfs(int u,int v)
{
if(vis[u]==1)
{
vis[u]=2;flag[u]=1;
c[++ttt]=u;
return 1;
}
vis[u]=1;
for(int i=h[u];i!=-1;i=ne[i])
{
if(i!=((v-1)^1)+1 && dfs(e[i],i))
{
if(vis[u]!=2)
{
c[++ttt]=u;flag[u]=1;
dis[ttt]=dis[ttt-1]+w[i];
}
else
{
dis[0]=dis[1]-w[i];
return 0;
}
return 1;
}
}
return 0;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) h[i]=-1;
for(int i=1;i<=n;i++)
{
long long x,y;scanf("%lld%lld",&x,&y);
add(i,x,y);add(x,i,y);
}
for(int i=1;i<=n;i++)
{
if(!flag[i])
{
ttt=0;
int g=dfs(i,0);
solve();
}
}
printf("%lld",res);
}
|
