【每日一题0415】树上dfs+技巧

https://ac.nowcoder.com/acm/problem/14248

技巧：偶 = 偶 + 偶 = 奇 + 奇。
偶数层到偶数层的节点路径长度为偶数，奇数层到奇数层的节点路径长度为偶数，
算出每个节点的深度，统计深度为奇、偶数的节点个数odd、even。
答案就是
树上dfs直接统计深度就可以了

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 100005
ll n,tot,rt,dis[N],fa[N],h[N],ne[N<<1],p[N<<1],wi[N<<1];
void addEdge(int u,int v,int w){p[++tot]=v;ne[tot]=h[u];h[u]=tot;wi[tot]=w;}
void add(int u,int v){p[++tot]=v;ne[tot]=h[u];h[u]=tot;}
ll odd,even;
void dfs(int u,int fa,int dep){
    if(dep&1) odd++;
    else even++;
    for(int i=h[u];i;i=ne[i])if(p[i]!=fa){
        dfs(p[i],u,dep+1);
    }
}
int main(){
    int n;cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        add(x,y);add(y,x);
    }
    dfs(1,0,0);
    cout<<odd*(odd-1)/2+even*(even-1)/2;
    return 0;
}