比赛 20241128 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 猴猴的比赛 最终得分 100
用户昵称 健康铀 运行时间 0.574 s
代码语言 C++ 内存使用 3.02 MiB
提交时间 2024-11-28 10:06:09
显示代码纯文本
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 100000 + 5;

int n, c, a[N], b[2 * N], p[2 * N], d, m[N], n1[N], t[N], r[N];

void add(int x, int y) {
    b[++c] = a[x]; a[x] = c; p[c] = y;
    b[++c] = a[y]; a[y] = c; p[c] = x;
}

void dfs1(int x, int y) {
    m[x] = ++d;
    n1[x] = 1;
    for (int i = a[x]; i; i = b[i]) {
        int z = p[i];
        if (z == y) continue;
        dfs1(z, x);
        n1[x] += n1[z];
    }
}

void update(int x, int v) {
    for (; x <= n; x += x & -x) t[x] += v;
}

int query(int x) {
    int s = 0;
    for (; x; x -= x & -x) s += t[x];
    return s;
}

void dfs(int x, int y) {
    int s = 0;
    for (int i = a[x]; i; i = b[i]) {
        int z = p[i];
        if (z == y) continue;
        s = query(m[z] + n1[z] - 1) - query(m[z] - 1);
        dfs(z, x);
        r[z] -= s;
        update(m[z], 1);
    }
    r[x] = query(m[x] + n1[x] - 1) - query(m[x] - 1);
}

int main() {
	freopen("monkeyclim.in","r",stdin);
	freopen("monkeyclim.out","w",stdout);
    int x, y;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    
    dfs1(1, 0);
    c = 0;
    memset(a, 0, sizeof(a));
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    
    dfs(1, 0);
    for (int i = 1; i <= n; i++) r[0] += r[i];
    printf("%d", r[0]);
    return 0;
}