【每日一题】Treepath

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

#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);
        //因为这棵树是无向的，所有要排除是父节点的可能
}