Codeforces 685B - Kay and Snowflake

#图论 #树 #树的重心
Published on 2016-06-24

题目地址

描述

给出一个 n(n≤300000)n(n\le 300000) 个点的树，以及 q(q≤300000)q(q\le 300000) 个询问，每个询问给出一个节点 uu，请你求 uu 的子树的重心。

分析

显然 n,qn, q 同级别，那么我们必须考虑在合理的时间内，求出树中所有点的重心。

重心：去掉这个点，那么所有的联通块的大小都不超过整个树大小的一半。
性质：把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。
证明：我们考虑将某个重心移动一步，可以发现，移动到任何非“原来两个树的重心的路径”上的点，都会使得答案大于移动到“原来两个树的重心的路径”上的点，所以新的树的重心在连接原来两个树的重心的路径上。

那么这个算法就十分清晰了，我们递归来做：

  1. 一个点的树的重心是他自己。
  2. 如果一棵树的根的所有子树大小都不超过整个树大小的一半，那么树根是重心。
  3. 否则找到子树大小超过整个树大小的一半的子树（只会有一个），假定当前树的重心为子树的重心，用调整的方式得到当前树的重心。

由于每个点最多被调整一次，所以复杂度是 O(n)O(n) 的。

代码

//  Created by Sengxian on 6/24/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 685B 重心递推
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 300000 + 3;
vector<int> G[maxn];
int n, q, fa[maxn], cen[maxn], s[maxn];

int dfs(int u) {
    s[u] = 1;
    for (int i = 0; i < (int)G[u].size(); ++i) s[u] += dfs(G[u][i]);
    if (s[u] == 1) cen[u] = u; //如果只有一个点，那么重心肯定是自己。
    else {
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (s[v] * 2 >= s[u]) { //重心只能在子树大小大于 s[u] 一半中。
                cen[u] = cen[v];
                while ((s[u] - s[cen[u]]) * 2 > s[u]) cen[u] = fa[cen[u]]; //重心会向 u 的方向移动，我们暴力移动即可。
            }
        }
        if (cen[u] == -1) cen[u] = u; //没有大于一半的子树，那么它自己就是重心
    }
    return s[u];
}

int main() {
    n = ReadInt(), q = ReadInt();
    for (int i = 1; i < n; ++i) {
        fa[i] = ReadInt() - 1;
        G[fa[i]].push_back(i);
    }
    memset(cen, -1, sizeof (int) * n);
    dfs(0);
    for (int i = 0; i < q; ++i) {
        int u = ReadInt() - 1;
        printf("%d\n", cen[u] + 1);
    }
    return 0;
}
Codeforces 682D - Alyona and Strings