NC14248-Treepath

题意：给定n个顶点的树，输出长度为偶数的路径数；
思路：树的各个顶点交替标记-1,1，易知标记相同的两个点之间的路径长度为偶数，统计-1,1的个数，再输出组合数就行了。
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int vis[N],n;
ll a,b;
vector<int> G[N];
void add(int x,int y)
{
    G[x].push_back(y);
    G[y].push_back(x);
}
void read()
{
    int x,y;
    cin>>n;
    for(int i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y);
}
void dfs(int u,int pre)
{
    vis[u]=-vis[pre];
    if(vis[u]==1) a++;
    else b++;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==pre) continue;
        dfs(v,u);
    }
}
void slove()
{
    a=0,b=0;vis[0]=-1;
    dfs(1,0);
    printf("%lld\n",a*(a-1)/2+b*(b-1)/2);
}
int main()
{
    read();
    slove();
    return 0;
}