题目

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

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

输出描述：
一行一个整数表示答案。

解析

听说这道题大佬们还阔以用树形dp，反正我是不会orz。
所以我也就直接就是dfs啦。
  1. 首先要储存树的结构，因为树的形状和根节点都是未知的，所以用树的孩子表示法存起来。（我这里用vector容器做的二维数组做邻接表，邻接矩阵用的麻烦）
  2. 其次我们就要想一下题目的意思了，简单来说就是任意两点之间的距离为偶数的组合数量，所以假设确定有一个根节点，
    到根节点的距离都是偶数的两个点，或者到根节点距离都是奇数的两个点就可以成为一组。（奇数+偶数=奇数，所以不算这种情况）
    所以我们只需要求出到我们确定的根节点的奇数节点数量和偶数节点数量就行了。
  3. 然后我们就来算奇数（odd）偶数（even）的大小惹，简单来说就是深搜一遍，看层数就知道是奇偶了。
    （ps：本人一开始还傻了吧唧的忘了根节点也是偶数节点，纠结了好久好久。）
  4. 接下来我们要办的就是数***算了，从数中任选两个数不就是组合数吗，所以奇偶均用求出组合数。

配图

不管看不看图，总感觉有张图会更好理解，hhh

AC代码 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int MAX = 1e5 + 9;
ll odd = 0, even = 0;//记录奇数与偶数
vector<ll> Node[MAX];//用vector容器模拟邻接表

void dfs(ll root, ll fa, ll depth);//深度优先遍历探测所有子节点深度，root为当前根节点，fa为当前根的父节点

int main() {
    js;
    ll n; cin >> n;
    for (ll i = 1; i < n; i++) {
        ll x, y; cin >> x >> y;
        Node[x].push_back(y);
        Node[y].push_back(x);
    }
    //完成树的无向连接，用树的孩子表示法表示
    dfs(1, -1, 0);
    cout << odd * (odd - 1) / 2 + even * (even - 1) / 2 << endl;
    return 0;
}

void dfs(ll root, ll fa, ll depth) {
    if (depth & 1) odd++;
    else even++;
    for (ll i = 0; i < Node[root].size(); i++)
        if (Node[root][i] != fa)
            dfs(Node[root][i], root, depth + 1);
        //因为这棵树是无向的，所有要排除是父节点的可能
}