A40871. 套娃
填空题
困难
知识点
题目描述
套娃
题目描述
输入
5 5
5 3
5 4
3 2
3 1
Q 1
Q 4
P 2
Q 1
Q 4
输出
2
1
2
0
0
参考答案
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
const int maxn = 1e5 + 10;
int n, m;
int head[maxn], to[maxn << 1], nxt[maxn << 1], val[maxn << 1];
int tot;
void add(int a, int b) {
to[++tot] = b;
nxt[tot] = head[a];
head[a] = tot;
}
int N;
int fa[maxn << 1][21 + 1];//节点u的2^k祖先
int depth[maxn << 1];
bool link[maxn << 1];
void dfs1(int u, int x) {//预处理fa[u][k]倍增
fa[u][0] = x;
depth[u] = depth[x] + 1;
for (int i = 1; i <= 21; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v == x) continue;
//fa[v][0] = u;
dfs1(v, u);
}
}
int solve(int x) {//寻找第一个断开的边
for (int i = N; ~i; i--) {
if (fa[x][i] && link[fa[x][i]] == 0) x = fa[x][i];
}
return x;
}
int rd[maxn << 1], rt;
int main() {
scanf("%d%d", &n, &m);
N = log2(n);
for (int i = 1; i <= n - 1; i++) {
int u, v;
scanf("%d%d", &u, &v);
rd[v]++;
add(u, v);
add(v, u);
}
for (int i = 1; i <= n; i++)
if (!rd[i]) {
rt = i;
break;
}
dfs1(rt, 0);
link[rt] = 1;
while (m--) {
char ch;
int t;
std::cin >> ch;
scanf("%d", &t);
if (ch == 'P') {
if (link[t]) {//已经断开
for (int i = head[t]; i; i = nxt[i])
link[to[i]] = 1;
puts("0");
continue;
}
int top = solve(t);
int father = fa[top][0];
printf("%d\n", depth[t] - depth[father]);
for (;; t = fa[t][0]) {
link[t] = 1;
for (int i = head[t]; i; i = nxt[i])
link[to[i]] = 1;
if (t == father) break;
}
} else {
if (link[t]) {
puts("0");
continue;
}
int top = solve(t);
int father = fa[top][0];
printf("%d\n", depth[t] - depth[father]);
}
}
return 0;
}答案解析
上一题
下一题