比赛 |
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;
}