题目：

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

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

输入描述:

第一行一个数n表示点的个数； 接下来n-1行，每行两个整数x，y表示边； 保证输入数据形成一棵树； 1<=n<=100000

输出描述:

一行一个整数表示答案。

示例1

输入

31 21 3

输出

 1

 

思路：

 

代码：

#include 
          
           #include 
           
            using namespace std;const int N = 1e5 + 1;int x = 0, y = 0;vector
            
              a[N];bool marked[N];void dfs(int v, int len){    marked[v] = true;    if(len % 2 == 0)        x++;    else         y++;    for(int i = 0; i < a[v].size(); i++)    {        if(marked[a[v][i]])            continue;        dfs(a[v][i], ++len);        len--;        }    }int main(){    int n;    int v,w;    cin >> n;    for(int i = 0; i < n-1; i++)    {        cin >> v >> w;        a[v].push_back(w);            a[w].push_back(v);        }    dfs(1,0);    long long ans = (long long)(x-1)*x/2 + (long long)(y-1)*y/2;    printf("%lld\n", ans);    return 0;}