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; }
|