A-Treepath//dfs

题目：

A-Treepath

时间限制：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

输入

3
1 2
1 3

输出

 1

 

思路：

 

代码：

#include <iostream>
#include <vector>

using namespace std;
const int N = 1e5 + 1;
int x = 0, y = 0;
vector<int> 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;
}