Codeforces 685B Kay and Snowflake

发表于 分类于 Disqus：

链接

传送门

题意

给出一个\(n\)个结点的树，有\(q\)个查询，对于每个查询输出以\(x\)为根的子树的重心。

思路

在两个树合并后，新的重心在链接原来两个树重心的路径上。因此可以dfs求解。

可以参考这篇博客：Codeforces 685B - Kay and Snowflake | Sengxian's Blog

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int maxn = 300005;

int p[maxn];
int sum[maxn], ans[maxn];
vector<int> g[maxn];

int dfs(int u) {
  sum[u] = 1;
  for (int v: g[u]) {
    sum[u] += dfs(v);
  }
  for (int v: g[u]) {
    if ((sum[v] << 1) >= sum[u]) {
      ans[u] = ans[v];
      while (((sum[u] - sum[ans[u]]) << 1) > sum[u]) {
        ans[u] = p[ans[u]];
      }
    }
  }
  if (ans[u] == 0) {
    ans[u] = u;
  }
  return sum[u];
}

int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; ++i) {
    scanf("%d", &p[i]);
    g[p[i]].push_back(i);
  }
  dfs(1);
  while (q--) {
    int x;
    scanf("%d", &x);
    printf("%d\n", ans[x]);
  }
  return 0;
}
相关文章