【每日一题】Treepath

这个其实是个水题，我们要找树当中所有长度为偶数的路径数目，我们其实可以很快的想到一点就是，我们dfs记录下每一个节点的层数，偶数层到偶数层距离一定为偶数，奇数层到奇数层的路径长度一定为偶数，这一点比较像奇数和奇数相差偶数，偶数和偶数相差为偶数。那么我们就只要dfs记录下来奇数层个数，偶数层个数，然后只要在奇数层选两个点选的方案数量加上偶数层两个点选的方案数量就是最终答案了，以防万一还是要开long long的~

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n;
ll ans=0,ou,ji;
vector<int> e[100010];
void dfs(int u,int fat,int deep)
{
    if(deep%2) ji++;
    else ou++;

    for(auto x:e[u]){
        if(x!=fat)
            dfs(x,u,deep+1);
    }


}
int main()
{
    cin>>n;
    for(int i=0;i<n-1;i++) {
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,0,1);
    if(ji>=2){
        ans+=1ll*ji*(ji-1)/2;
    }
    if(ou>=2) ans+=1ll*(ou-1)*ou/2;
    cout<<ans<<endl;
    return 0;
}