Treepath

链接：https://ac.nowcoder.com/acm/problem/14248
来源：牛客网

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

是偶数，所以只要为偶数即可
于是预处理所有，即到根的距离
最后计算和自己奇偶性相同的数量，加起来即可

:

#include <bits/stdc++.h>
#define ri int
#define ll long long
using namespace std;
const int Maxn=1e5;
int lt[Maxn+5],nt[2*Maxn+5],ed[2*Maxn+5],d[Maxn+5],n,cnt;
inline void addedge(int x,int y) {
    ed[++cnt]=y;nt[cnt]=lt[x];lt[x]=cnt;
}
void dfs(int u,int fa,int dis) {
    d[u]=dis;
    for(ri i=lt[u];i;i=nt[i])
        if(ed[i]!=fa)dfs(ed[i],u,dis+1);
}
int main() {
    scanf("%d",&n);
    for(ri i=1;i<n;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    dfs(1,0,0);
    ll ans=0;
    int cnt[2]={0};
    for(ri i=1;i<=n;i++) {ans+=cnt[d[i]%2];++cnt[d[i]%2];}
    printf("%lld\n",ans);
    return 0;
}