【每日一题】Treepath

题上要求找长度为偶数的路径。根据常识可知 偶 = 偶 + 偶 = 奇 + 奇。
所以我们可以考虑深度，算出每个节点的深度，深度为偶数的和偶数组合，深度奇数的和奇数组合。
因为x到y和y到x属于一条路，不考虑顺序，所以答案是个组合数。
也是就
其中a、b分别为深度为奇、偶数的节点个数
注意结果炸int

#include<bits/stdc++.h>
using namespace std;
vector<int>e[1<<17];
long long a,b;
void dfs(int x,int f,int dep){
    if(dep&1) a++;
    else b++;
    for(auto it:e[x]){
        if(it==f) continue;
        dfs(it,x,dep+1);
    }
}
int main(){
    int n;cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,0,0);
    cout<<a*(a-1)/2+b*(b-1)/2;
    return 0;
}