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;
typedef long long ll;
const int mxn=1e6+5;
int read()
{
int ret=0;char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')ret=ret*10+c-'0',c=getchar();
return ret;
}
int n,fa[mxn],son[mxn],dep[mxn],son2[mxn],dep2[mxn];
struct edge
{
int nxt,to;
}e[mxn<<1];int t[mxn],cnt;
void ad(int u,int v)
{
e[++cnt].to=v,e[cnt].nxt=t[u],t[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=t[v],t[v]=cnt;
}
void dfs(int x,int f)
{
fa[x]=f;
for(int i=t[x];i;i=e[i].nxt)if(e[i].to!=f)
{
dfs(e[i].to,x);
if(dep[e[i].to]>dep[son[x]])son2[x]=son[x],son[x]=e[i].to;
else if(dep[e[i].to]>dep[son2[x]])son2[x]=e[i].to;
}
dep[x]=dep[son[x]]+1,dep2[x]=dep[son2[x]]+1;
}
ll _2(ll _1_,ll _2_)
{
ll ret=_1_*_1_-_2_;
return ret/2LL;
}
ll _3(ll _1_,ll _2_,ll _3_)
{
ll ret=_1_*_1_*_1_+2LL*_3_-3LL*_1_*_2_;
return ret/6LL;
}
ll buf[mxn];ll *now=buf,*f[mxn];
ll buf2[mxn],b1[mxn],b2[mxn],ans;
ll buf3[mxn],*won=buf3,*ff[mxn];
void dp1(int x)
{
f[x]=++now;
f[x][0]=1LL;
if(son[x])
{
dp1(son[x]);
ff[son[x]]=++won;
for(int i=0;i<dep2[x]-1;i++)ff[son[x]][i]=f[son[x]][i],++won;
}
for(int i=t[x];i;i=e[i].nxt)if(!f[e[i].to])
{
dp1(e[i].to);
for(int j=0;j<dep[e[i].to];j++)f[x][j+1]+=f[e[i].to][j];
}
if(son2[x])
{
for(int i=0;i<dep2[x]-1;i++)b1[i]+=ff[son[x]][i]*ff[son[x]][i],b2[i]+=ff[son[x]][i]*ff[son[x]][i]*ff[son[x]][i];
for(int i=t[x];i;i=e[i].nxt)if(e[i].to!=fa[x]&&e[i].to!=son[x])for(int j=0;j<dep[e[i].to];j++)b1[j]+=f[e[i].to][j]*f[e[i].to][j],b2[j]+=f[e[i].to][j]*f[e[i].to][j]*f[e[i].to][j];
for(int i=0;i<dep2[x]-1;i++)
{
ans+=_3(f[x][i+1],b1[i],b2[i]);
(*(f[son2[x]]-buf+buf2+i))=_2(f[x][i+1],b1[i]);
b1[i]=b2[i]=0LL;
}
}
if(son[x])won=ff[son[x]]-1;
if(son2[x])for(int i=1;i<dep2[x];i++)f[son2[x]][i-1]=f[x][i];
}
ll fub[mxn<<1];ll *g[mxn];
void dp2(int x,bool flag)
{
if(!son[x])return;
if(!flag)
{
now-=((dep[x]<<1)|1);
g[x]=now+dep[x];
if(fa[x])for(int i=1;i<dep[x];i++)g[x][i]=g[fa[x]][i-1];
}
else g[x]=g[fa[x]]-1;
g[x][0]=1LL;
if(fa[x])
{
for(int i=2;i<=dep2[fa[x]]&&i<dep[x];i++)
g[x][i]+=f[son2[fa[x]]][i-2];
if(dep2[fa[x]]>1)--g[x][2];
int y=x,h=0;
for(int i=3;i<=dep2[fa[x]]&&i<dep[x];i++)
{
while(i-3-h>=dep2[y]-1)y=son[y],++h;
if(i-3-h<0)g[x][i]--;
else g[x][i]-=f[son2[y]][i-3-h];
}
}
if(fa[x]&&son2[x])for(int i=0;i<dep2[x]-1;i++)
ans+=g[x][i+1]*(*(f[son2[x]]-buf+buf2+i));
for(int i=t[x];i;i=e[i].nxt)if(e[i].to!=fa[x]&&e[i].to!=son[x])
{
dp2(e[i].to,0);
}
dp2(son[x],1);
}
int main()
{
n=read();
for(int i=1,x,y;i<n;i++)x=read(),y=read(),ad(x,y);
dfs(1,0);
dp1(1);
now=fub+(mxn<<1);
dp2(1,0);
printf("%lld",ans);
return 0;
}
|
