【题解】CF 860E Arkady and a Nobody-men

请注意,本文编写于 100 天前,最后修改于 100 天前,其中某些信息可能已经过时。

Problem

给定一棵树,定义:

$$ f(x,y)=\sum_{p\in subtree(y),p\neq y}[dep[p]\leq dep[x]]\\ g(x)=\sum_{x\in subtree(p),p\neq x}f(x,p) $$

求 $g(i)$

Thought

用人话来描述要求的东西就是:求每个点的祖先节点的子树中深度小于等于该点的总点数

考虑每个点 $y$ 对 $g(x)$ 的贡献, $y$ 有贡献当且仅当 $dep[y]\leq dep[x]$ ,其贡献大小为 $dep[lca(x,y)]$ ,也就是是说在 $x,y$ 的所有公共祖先处均有 $1$ 的贡献

即: $g(x)=\sum_{y\neq x,dep[y]\leq dep[x]}dep[lca(x,y)]$

将 $dep[y]\leq dep[x]$ 这个条件拆为 $dep[y]=dep[x]$ 和 $dep[y]<dep[x]$ ,发现:

$$ g(x)=g(fa[x])-dep[fa[x]]+\sum_{y\neq x,dep[y]=dep[x]}dep[lca(x,y)] $$

那么只需要求出 $h(x)=\sum_{y\neq x,dep[y]=dep[x]}dep[lca(x,y)]$ 即可

考虑使用长链剖分,设当前点为 $x$ ,合并根为 $y$ 的子树,那么所有 $x$ 树中深度为 $k$ 的节点答案需要加上 $y$ 树中深度为 $k-1$ 的节点数 $*dep[x]$,反过来 $y$ 树中的节点同样会受到 $x$ 树中节点的影响

容易发现合并之后,所有深度相同的点以后受到的贡献也必然相同

所以如果我们用一棵树储存深度为 $k$ 的节点,设 $x$ 树中深度为 $k$ 的树为 $A$,根为 $a$ , $y$ 树中深度为 $k-1$ 的树为 $B$ ,根为 $b$ ,我们连一条边 $a\to b$ ,权值为 $h(b)-h(a)$ ,使得 $B$ 成为 $A$ 的子树,恰好 $h(b)$ 和 $h(a)$ 的差值为边的权值,所以说最后对树进行 $BFS$ 即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 500010;
ll *f[N];
ll h[N], g[N];
int siz[N], fa[N], son[N], len[N], dep[N];
int n, rt;
struct Graph {
    int head[N], t[N << 1], n[N << 1], w[N << 1], tot;
    void addedge(int u, int v) {
        ++ tot;
        t[tot] = v;
        n[tot] = head[u];
        head[u] = tot;
    }
    void addedge(int u, int v, int d) {
        ++ tot;
        t[tot] = v;
        n[tot] = head[u];
        w[tot] = d;
        head[u] = tot;
    }
}G, H;
void dfs1(int x) {
    dep[x] = dep[fa[x]] + 1;
    for(int i = G.head[x]; i; i = G.n[i]) {
        int t = G.t[i]; dfs1(t);
        if(len[t] > len[son[x]]) son[x] = t;
    }
    len[x] = len[son[x]] + 1;
}
void arrange() {
    for(int i = 1; i <= n; ++ i)
        if(son[fa[i]] != i)
            f[i] = new ll[len[i] + 1];
}
void dfs2(int x, ll *F) {
    if(son[x]) dfs2(son[x], F + 1);
    for(int i = G.head[x]; i; i = G.n[i]) {
        int t = G.t[i];
        if(t == son[x]) continue;
        dfs2(t, f[t]);
        for(int j = 0; j < len[t]; ++ j) {
            h[F[j + 1]] += 1ll * dep[x] * siz[f[t][j]];
            h[f[t][j]] += 1ll * dep[x] * siz[F[j + 1]];
            siz[F[j + 1]] += siz[f[t][j]];
            H.addedge(F[j + 1], f[t][j], h[f[t][j]] - h[F[j + 1]]);
        }
    }
    F[0] = x;
    siz[F[0]] = 1;
}
void dfs3(int x) {
    for(int i = H.head[x]; i; i = H.n[i]) {
        int t = H.t[i];
        ll w = H.w[i];
        h[t] = h[x] + w;
        dfs3(t);
    }
}
void dfs4(int x) {
    for(int i = G.head[x]; i; i = G.n[i]) {
        int t = G.t[i];
        g[t] = g[x] + dep[x] + h[t];
        dfs4(t);
    }
}
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in", "r", stdin);
    #endif
    n = read();
    for(int i = 1; i <= n; ++ i) {
        fa[i] = read();
        if(fa[i]) G.addedge(fa[i], i);
        else rt = i;
    }
    dfs1(rt);
    arrange();
    dfs2(rt, f[rt]);
    for(int i = 0; i < len[rt]; ++ i)
        dfs3(f[rt][i]);
    dfs4(rt);
    for(int i = 1; i <= n; ++ i)
        printf("%lld\n", g[i]);
    return 0;
}
Comments

添加新评论