Codeforces 1009F(树上启发式合并)

发表于 | 分类于 | | + s

Codeforces 1011D
题意：给出一棵有根树，对于每个节点$x$，定义一个无穷序列$d$，其中$d(x,i)$表示以$x$为根节点的子树中到$x$的距离恰好为$i$的点的个数，$i \in [0， INF]$，现在对每个点$x$，希望求出一个东西$j$，使得对于任意$k < j$，$d(x,k) < d(x,j)$，对于任意$k > j,d(x,k) \leq d(x,j)$

本题类似于CF600E
其实就是对每个点求出这个点子树的的某层节点最多的那层。
考虑将层作为颜色，维护子树中颜色最多的那个颜色。
那么这里没有修改，并且也是子树操作，那么我们可以考虑用树上启发式合并。
也就是将树轻重链剖分(求出重儿子)，然后对于每个点，先遍历所有的轻儿子子树，然后再回退所有当前答案，然后遍历重儿子子树，不回退答案，然后再直接遍历所有的轻儿子子树，不回退答案，并且不管下面的轻重链了。
那么这题就是一个裸题了，注意用map方便。
更新答案方式类似莫队。
复杂度证明：
引理1：

根节点到树上任意节点的轻边数不超过$\log n$条。

证明：我们设根到该节点有$x$条轻边, 该节点的子树大小为$y$，显然轻边连接的子节点的子树大小小于父亲的一半（若大于一半就不是轻边了），则 $y < n/2^x$，显然$ n > 2^x$所以 $x > \log n$

一个节点的被遍历的次数等于他到根节点路径上的轻边树$+1$

证明：显然，只要上面有一条轻边下面才会被遍历一次

综上，时间复杂度大约为$O(\log n)$

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 1000000 + 5;

    vector<int > G[MAXN];

    int n, son[MAXN], siz[MAXN], dep[MAXN];
    int pos, ans[MAXN];
    map<int, int > ma;

    void dfs_son(int u, int fa) {
        siz[u] = 1, dep[u] = dep[fa] + 1;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) {
                dfs_son(v, u);
                siz[u] += siz[v];
                if (son[u] < 0 || siz[son[u]] < siz[v])
                    son[u] = v;
            }
        }
    }
    void add(int u, int fa) {
        ++ma[dep[u]];
        if (ma[dep[u]] > ma[dep[pos]] || (ma[dep[u]] == ma[dep[pos]] && dep[u] < dep[pos])) pos = u; 
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) add(v, u);
        }
    }
    void dfs_dsu(int u, int fa) {
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v == son[u]) continue ;
            if (v == fa) continue ;
            dfs_dsu(v, u);
            ma.clear(), pos = 0;
        }
        if (son[u] >= 0) dfs_dsu(son[u], u);
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v == son[u]) continue ;
            if (v == fa) continue ;
            add(v, u);
        }
        ++ma[dep[u]];
        if (ma[dep[u]] > ma[dep[pos]] || (ma[dep[u]] == ma[dep[pos]] && dep[u] < dep[pos])) pos = u; 
        ans[u] = dep[pos] - dep[u];
    }

    void clean() {
        ms(son, -1), ms(siz, 0), ms(dep, 0), pos = 0, ms(ans, 0);
    }
    int solve() {

        clean(); 

        scanf("%d", &n);
        for (int u, v, i = 1; i < n; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v), G[v].push_back(u);
        }

        dfs_son(1, 0);
        dfs_dsu(1, 0);

        for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------