题意

给出一棵树，问长度为偶数的路径数有多少。

思路

记录路径长度为奇数的数目和为偶数的数目，然后 n * (n-1) / 2 求和即可。

#include 
    
     using namespace std;const int N = 1e5 + 11;const int INF = 0x3f3f3f3f;vector
     
       e[N];int n, dis[N];long long id[2];void dfs(int u, int fa) {    id[dis[u]%2]++;    for(int i = 0; i < e[u].size(); i++) {        int v = e[u][i];        if(v == fa) continue;        dis[v] = dis[u] + 1;        dfs(v, u);    }}int main() {    scanf("%d", &n);    for(int i = 1; i < n; i++) {        int u, v; scanf("%d%d", &u, &v);        e[u].push_back(v);        e[v].push_back(u);    }    dis[1] = 0;    dfs(1, 0);    long long ans = id[0] * (id[0] - 1) / 2 + id[1] * (id[1] - 1) / 2;    printf("%lld\n", ans);    return 0;}