CF 1009F Dominant Indices

题目描述

https://codeforces.com/problemset/problem/1009/F

简要题解：给定一棵 $n$ 个节点的有根树，我们定义 $f_{u,k}$ 为 $u$ 的子树内距离 $u$ 为 $k$ 的点的个数，对于每个节点 $u$ 求 $f_{u,k}$ 最大的 $k$

$n\le 10^6$

Solution

我们在 $dp$ 的时候先 $dp$ 长儿子，那么将长儿子的 $dp$ 合并到点 $u$ 只需要右移一位，这个可以用指针实现，除了长儿子以外直接暴力即可，时间复杂度为 $O(n)$

#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 1000010
#define ll long long
using namespace std;

int n; 

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int dep[maxn], mxd[maxn], son[maxn], len[maxn];
void pre(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        mxd[v] = dep[v] = dep[u] + 1;
        pre(v, u);
        if (mxd[v] > mxd[son[u]]) son[u] = v;
        mxd[u] = max(mxd[u], mxd[v]); 
    } len[u] = mxd[u] - dep[u];
}

int buf[maxn], *now = buf;
int *newbuf(int n) { int *res = now; now += n; return res; } 

int *f[maxn], ans[maxn];
void dfs(int u, int fa) {
    f[u][0] = 1; 
    if (son[u]) {
        f[son[u]] = f[u] + 1;
        dfs(son[u], u);
        ans[u] = ans[son[u]] + 1; 
    }
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue;
        f[v] = newbuf(len[v] + 1); dfs(v, u);
        for (int k = 1; k <= len[v] + 1; ++k) { 
            f[u][k] += f[v][k - 1];
            if (f[u][k] > f[u][ans[u]] ||
                f[u][k] == f[u][ans[u]] && k < ans[u]) ans[u] = k;
        }
    } if (f[u][ans[u]] == 1) ans[u] = 0; 
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y), add_edge(y, x); 
    } mxd[1] = dep[1] = 1, pre(1, 0), f[1] = newbuf(len[1] + 1), dfs(1, 0);
    for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
    return 0;
}