题解 | #Treepath#

考察知识点：树上 DFS

设节点 i 到根节点 1 的距离为节点 i 的长度，记为 dist[i]，则有以下结论：

• 长度为偶数的两个节点之间的路径长度一定为偶数
• 长度为奇数的两个节点之间的路径长度也一定为偶数

因此本题我们只需要遍历整棵树，记录每个节点的长度，然后统计长度为偶数的节点数量 和长度为奇数的节点数量 ，长度为偶数的路径的数量即为 。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

const int N = 1e6 + 5;

vi edges[N];
int dist[N];

void dfs(int u, int from)
{
    dist[u] = dist[from] + 1;
    for (int v : edges[u])
        if (v != from)
            dfs(v, u);
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs(1, 0);
    ll cnt[2] = {0, 0};
    for (int i = 1; i <= n; i++)
        cnt[dist[i] % 2]++;
    cout << cnt[0] * (cnt[0] - 1) / 2 + cnt[1] * (cnt[1] - 1) / 2 << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}