cf1060E. Sergey and Subway(树形dp)

题意

题目链接

Sol

很套路的题

直接考虑每个边的贡献，最后再把奇数点的贡献算上

#include<bits/stdc++.h>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

#define int long long

#define LL long long

#define rg register

#define pt(x) printf("%d ", x);

#define Fin(x) {freopen(#x".in","r",stdin);}

#define Fout(x) {freopen(#x".out","w",stdout);}

#define chmin(x, y) (x = x < y ? x : y)

using namespace std;

const int MAXN = 1e6 + 10, INF = 1e18 + 10, mod = 1e9 + 7;

const double eps = 1e-9;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, dep[MAXN], num[MAXN], siz[MAXN], ans, a2;

vector<int> v[MAXN];

void dfs(int x, int fa) {

    dep[x] = dep[fa] + 1;

    num[dep[x] & 1]++;

    siz[x] = 1;

    for(int i = 0; i < v[x].size(); i++) {

        int to = v[x][i]; if(to == fa) continue;

        dfs(to, x);

        siz[x] += siz[to];

    }

    for(int i = 0; i < v[x].size(); i++) {

        int to = v[x][i]; if(to == fa) continue;

        ans += siz[to] * (N - siz[to]);

    }

}

main() {

    N = read();

    for(int i = 1; i <= N - 1; i++) {

        int x = read(), y = read();

        v[x].push_back(y); v[y].push_back(x);

    }

    dfs(1, 0);

    for(int i = 1; i <= N; i++) a2 += num[(dep[i] & 1) ^ 1];

    printf("%lld", (ans + a2 / 2) / 2);

    return 0;

}