【CF1009F】 Dominant Indices （长链剖分+DP）

题目链接

\(O(n^2)\)的\(DP\)很容易想，\(f[u][i]\)表示在\(u\)的子树中距离\(u\)为\(i\)的点的个数，则\(f[u][i]=\sum f[v][i-1]\)

长链剖分。

\(O(1)\)继承重儿子的信息，再暴力合并其他轻儿子的信息，时间复杂度是线性的。

继承重儿子用指针实现，非常巧妙。

#include <cstdio>

int xjc; char ch;

inline int read(){

    xjc = 0; ch = getchar();

    while(ch < '0' || ch > '9') ch = getchar();

    while(ch >= '0' && ch <= '9'){ xjc = xjc * 10 + ch - '0'; ch = getchar(); }

    return xjc;

}

const int MAXN = 1000010;

struct Edge{

    int next, to;

}e[MAXN << 1];

int head[MAXN], num, son[MAXN], len[MAXN], *f[MAXN], tmp[MAXN], *id = tmp, ans[MAXN], n;

inline void Add(int from, int to){

    e[++num].to = to; e[num].next = head[from]; head[from] = num;

    e[++num].to = from; e[num].next = head[to]; head[to] = num;

}

void dfs(int u, int fa){

    for(int i = head[u]; i; i = e[i].next)

       if(e[i].to != fa){

         dfs(e[i].to, u);

         if(len[e[i].to] > len[son[u]])

           son[u] = e[i].to;

       }

    len[u] = len[son[u]] + 1;

}

void dp(int u, int fa){

    f[u][0] = 1;

    if(son[u]) f[son[u]] = f[u] + 1, dp(son[u], u), ans[u] = ans[son[u]] + 1;

    for(int i = head[u]; i; i = e[i].next)

       if(e[i].to != fa && e[i].to != son[u]){

         f[e[i].to] = id; id += len[e[i].to]; dp(e[i].to, u);

         for(int j = 1; j <= len[e[i].to]; ++j){

            f[u][j] += f[e[i].to][j - 1];

            if(f[u][j] > f[u][ans[u]] || f[u][j] == f[u][ans[u]] && j < ans[u])

              ans[u] = j;

         }

       }

    if(f[u][ans[u]] == 1) ans[u] = 0;

}

int main(){

    n = read();

    for(int i = 1; i < n; ++i)

       Add(read(), read());

    dfs(1, 0); f[1] = id; id += len[1];

    dp(1, 0);

    for(int i = 1; i <= n; ++i)

       printf("%d\n", ans[i]);

    getchar();

}