传送门

题意

给定一棵n个点的树，问其中有多少条长度为偶数的路径。

tags

• dfs/bfs
• 思维

分析

以节点开始，记录每个点的深度。设奇偶深度的点个数分别为：和，则ans=。
具体证明过程如下图：

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
int head[maxn], cnt;
int dep[maxn];
struct node {
    int v, next;
} e[maxn << 1];

void add(int u, int v) {
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void init() {
    memset(head, -1, sizeof(head));
    cnt = 0;
}

void dfs(int u, int v) {
    dep[u] = dep[v] + 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int x = e[i].v;
        if (v == x) continue;
        dfs(x, u);
    }
}

int main(void) {
    int n;
    init();
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1, 1);
    ll x = 0, y = 0;
    for (int i = 1; i <= n; i++) {
        if (dep[i] & 1) {
            x++;
        } else {
            y++;
        }
    }
    cout << (x - 1) * x / 2 + (y - 1) * y / 2 << endl;

    return 0;
}