Treepath题解

题意要理解通透，就是喊你找起点和终点（两个点）不能同时出现第二次，然后随机组合成路径的边为偶数，一看就是组合数了，我们首先可以这样统计奇偶数的边，因为奇数加奇数＝偶数，偶数加偶数=偶数，那么我们就可以统计每次DFS的深度奇偶统计，最后是不是就是一个C（2，奇数）+C（2，偶数）
注意，开longlong

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof b);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
vector<ll>ans[1<<17];
ll a,b;
ll dfs(ll u,ll fa,ll dep)
{
    if(dep&1) a++;
    else
        b++;
        for(int i=0;i<ans[u].size();i++)
        {
            if(ans[u][i]==fa)
                continue;
            dfs(ans[u][i],u,dep+1);
        }

}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        ans[a].push_back(b);
        ans[b].push_back(a);
    }
    dfs(1,0,0);
    cout<<a*(a-1)/2+b*(b-1)/2<<endl;
    return 0;
}