NC14248 Treepath

题目描述
给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。

思路：从一点开始dfs求出每个点的深度，分出奇点个数a、偶点个数b，根据奇数深度+奇数深度=偶数深度、偶数深度+偶数深度=偶数深度可以得出答案ans=a(a-1)/2+b(b-1)
代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
struct pp{
    int to,next;
}r[200005];
int head[100005];
int deg[100005];
int cnt;
ll a,b;
void add(int u,int v)
{
    deg[u]++;
    r[++cnt].to=v;
    r[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int ct,int fa)
{
    if(ct%2)
        a++;
    else
        b++;
    for(int i=head[u];i;i=r[i].next)
    {
        int v=r[i].to;
        if(v==fa)continue;
        dfs(v,ct+1,u);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    if(n<=2)
        printf("0\n");
    else
    {
        dfs(1,1,0);
        printf("%lld\n",a*(a-1)/2+b*(b-1)/2);
    }
    return 0;
}