NC14248 Treepath

题意

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

分析

这就是一道水题。。。
考虑一条路径 ，长度为
因为 为偶数，于是只用看 为偶数的对数即可。
统计深度为奇数的点数 ，为偶数的点数为
答案为

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 100005
using namespace __gnu_pbds;
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
struct node{
    int a, b, n;
}d[N * 2];
int h[N], cnt, fa[N], dep[N];
void cr(int a, int b){
    d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a){
    int i, b;
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        if(b == fa[a]) continue;
        fa[b] = a;
        dep[b] = dep[a] + 1;
        dfs(b);
    }
}
int main(){
    int i, j, n, m, a, b, t1 = 0, t2;
    n = read();
    for(i = 1; i < n; i++){
        a = read(); b = read();
        cr(a, b); cr(b, a);
    }
    dfs(1);
    for(i = 1; i <= n; i++) t1 += (dep[i] & 1);
    t2 = n - t1;
    printf("%lld", z * t1 * (t1 - 1) / 2 + z * t2 * (t2 - 1) / 2);
    return 0;
}