Treepath

题意:求一棵n个点的树中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。
思路：奇+奇=偶，偶+偶=偶
所以用跑一遍dfs求出奇数深度结点的数目x和偶数深度结点的数目y
再计算偶数路径数=(x(x-1)+y(y-1))/2;

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define inf 998244353

int n;

vector<int> g[200005];

struct w
{
    int x, y;
};

struct w dfs(int v,int f)
{
    struct w w1, w2;
    w1.x=0;
    w1.y=1;
    for(int i=0; i<g[v].size(); i++)
    {
        if(g[v][i]==f)
        {
            continue;
        }
        w2=dfs(g[v][i],v);
        w1.x+=w2.y;
        w1.y+=w2.x;
    }
    return w1;
}

int main()
{
    scanf("%d",&n);
    for(int i=0; i<n-1; i++)
    {
        int s, e, cost;
        scanf("%d %d",&s,&e);
        g[s].push_back(e);
        g[e].push_back(s);
    }
    struct w w=dfs(1,-1);
    ll z=((ll)w.x*(w.x-1))+((ll)w.y*(w.y-1));
    printf("%lld\n",z/2);
    return 0;
}