随机游走

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Edge
{
int to;
int next;
}e[200005];
int n,m,edgenum,head[100005],d[100005],pa[100005];
ll f[100005],g[100005],ans,maxup[100005],maxdown[100005];
ll tmp[100005],top,max1[100005],max2[100005],tmp2[100005];
void add(int u,int v)
{
e[++edgenum].to=v;
e[edgenum].next=head[u];
head[u]=edgenum;
}
void dfs_f(int node)
{
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==pa[node])continue;
pa[to]=node;
dfs_f(to);
f[node]+=f[to];
}
f[node]+=d[node];
}
void dfs_g(int node)
{
if(node!=1)g[node]=g[pa[node]]+f[pa[node]]-f[node];
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==pa[node])continue;
dfs_g(to);
}
}
void dfs_tot(int node)
{
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==pa[node])continue;
dfs_tot(to);
maxup[node]=max(maxup[node],maxup[to]+f[to]);
maxdown[node]=max(maxdown[node],maxdown[to]+g[to]);
}
top=0;
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(to==pa[node])continue;
tmp[++top]=maxup[to]+f[to];
tmp2[top]=maxdown[to]+g[to];
}
for(int i=1;i<=top;i++)
max1[i]=max(max1[i-1],tmp[i]);
max2[top+1]=0;
for(int i=top;i>=1;i--)
max2[i]=max(max2[i+1],tmp[i]);
for(int i=1;i<=top;i++)
ans=max(ans,tmp2[i]+max(max1[i-1],max2[i+1]));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
d[u]++;
d[v]++;
}
dfs_f(1);
dfs_g(1);
dfs_tot(1);
printf("%lld.00000n",ans);
return 0;
}