每日一题 4.15 Treepath

这是一个简单的dfs
偶数=偶数+偶数或者奇数+奇数 所有我们只用统计深度为奇数或者偶数的个数
答案为 奇数或者偶数任取两个 即(ans1(ans1-1)/2)+(ans2(ans2-1)/2)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int head[N],nex[N<<1],to[N<<1],tot;
int n,h[N];
ll ans1,ans2;
void add(int a,int b){
    to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}

void dfs(int x,int fa){
    h[x]=h[fa]+1;
    if(h[x]&1) ans1++;
    else ans2++;
    for(int i=head[x];i;i=nex[i]){
        if(to[i]!=fa) dfs(to[i],x);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;    scanf("%d %d",&x,&y);    add(x,y);    add(y,x);
    }
    dfs(1,0);
    cout<<(ans1*(ans1-1)/2)+(ans2*(ans2-1)/2)<<endl;
    return 0;
}