记录编号	572228	评测结果	AAAAAAAAAA
题目名称	[CF1060E]Sergey and Subway	最终得分	100
用户昵称	ZRQ	是否通过	通过
代码语言	C++	运行时间	0.220 s
提交时间	2022-06-29 15:20:55	内存使用	8.29 MiB

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=400005;
int n,hd[N],e[N],nxt[N],idx,dep[N];
ll ans,tot1,tot2;
char ch;
inline void read(int &x){x=0;ch=getchar();while(ch<48||ch>57)ch=getchar();while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}
void add(int u,int v)
{
    nxt[++idx]=hd[u],hd[u]=idx,e[idx]=v;
}
int DFS(int nw,int fa)
{
    int sum=1;
    dep[nw]=dep[fa]+1;
    if(dep[nw]&1) ++tot1;
    else ++tot2;
    for(int i=hd[nw];i;i=nxt[i])
        if(e[i]!=fa)
        {
            int k=DFS(e[i],nw);
            sum+=k;
            ans+=1ll*k*(n-k);
        }
    return sum;
}
int main()
{
    freopen("Sergeyas.in","r",stdin);
    freopen("Sergeyas.out","w",stdout);
    read(n);
    int x,y;
    for(int i=1;i<n;++i) read(x),read(y),add(x,y),add(y,x);
    DFS(1,0);
    printf("%lld\n",(ans+1ll*tot1*tot2)/2);
    return 0;
}