Chlience

【题解】LOJ 2434 「ZJOI2018」历史
Problem给定一棵树,第 $i$ 个点可以将到根节点路径上染成第 $i$ 种颜色 $a_i$ 次每次染色过程中...
扫描右侧二维码阅读全文
15
2019/03

【题解】LOJ 2434 「ZJOI2018」历史

Problem

给定一棵树,第 $i$ 个点可以将到根节点路径上染成第 $i$ 种颜色 $a_i$ 次

每次染色过程中遇到一个新的颜色即产生一点新的贡献,求贡献最大值

有 $m$ 次修改操作,每次修改一个点的 $a_i$,求贡献最大值

Thought

显然的,在路径上遇到一种颜色仅仅会遇到连续的一段
那么可以计算在 $i​$ 点遇到新颜色时的贡献

同样的,在 $i$ 点某个子树中的节点互相之间不可能在 $i$ 点处产生贡献
那么,可以考虑将每个 $i$ 的子树合为一个点,计算子树(和 $i$ 点)之间相互的贡献

设每个 $i$ 点有 $num[i]$ 个儿子,每个子树的 $\sum a_i=b_{son[i]}$,那么相当于排列 $num[i] + 1$ 个 颜色的小球,每个小球有 $b_{son[i]}$ 个,两两相邻且颜色不同则产生一点贡献,求总贡献

设某种颜色的球最多有 $k$ 个,只需要保证这 $k$ 个球尽量不要相邻在一起,那么其他的球自然而然就不会相邻在一起
可以比较方便的计算出最终答案应该为 $min(siz-1,2(siz-k))$ ,其中 $2(siz-k)$ 的意思是其他颜色的球尽量分割开最多的球,每一个其他颜色的球产生 $2$ 的贡献

所以其实只需要一个 $DFS$ 就能解决静态问题
如果加入修改的话,那么每次就会使得一条链上的答案改变

问题来了,如何统计一条链上修改过后的答案呢?

考虑分界的情况,即 $siz-1=2(siz-k)$ 即 $2k=siz+1$
如果某个子树大小占到其父亲子树大小的一半以上,那么将其设为重边,否则设为轻边

如果一个点有重儿子,那么其贡献为 $2(siz-son)$ ,否则其贡献为 $siz - 1$

如果从一个重儿子向上更新,显然重儿子还是重儿子,并且贡献不变,上面的轻边可能会变成重边,用类似于 $LCT$ 的办法进行维护

对于轻边来说,不会超过 $log$ 条,暴力更新即可

维护子树大小就直接用 LCT 维护子树信息即可(轻边转移,重边数据结构)

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 = 400010;

struct Edge {
    int t, n;
}e[N << 1];
int head[N], Etot;
int n, m;
ll ans;

#define L ch[x][0]
#define R ch[x][1]
struct LCT {
    int fa[N], ch[N][2], dep[N];
    ll siz[N], vu[N], val[N];
    bool isr(int x) {return ch[fa[x]][0] != x && ch[fa[x]][1] != x;}
    bool pos(int x) {return ch[fa[x]][1] == x;}
    void upd(int x) {siz[x] = siz[L] + siz[R] + vu[x] + val[x];}
    void rotate(int x) {
        int f = fa[x], oldf = fa[f], w = pos(x);
        if(!isr(f))
            ch[oldf][ch[oldf][1] == f] = x;
        ch[f][w] = ch[x][w ^ 1]; fa[ch[f][w]] = f;
        ch[x][w ^ 1] = f; fa[f] = x;
        fa[x] = oldf;
        upd(f); upd(x);
    }
    void splay(int x) {
        for(int f; !isr(x); rotate(x))
            if(!isr(f = fa[x]))
                rotate(pos(x) == pos(f) ? f : x);
    }

    ll cal(int x) {
        if(R) return 2 * (siz[x] - siz[L] - siz[R]);
        return min(2 * (siz[x] - siz[L] - val[x]), siz[x] - siz[L] - 1);
    }
    void dfs(int x) {
        dep[x] = dep[fa[x]] + 1;
        siz[x] = val[x];
        for(int i = head[x]; i; i = e[i].n) {
            if(e[i].t == fa[x]) continue;
            fa[e[i].t] = x;
            dfs(e[i].t);
            siz[x] += siz[e[i].t];
        }
        for(int i = head[x]; i; i = e[i].n) {
            if(e[i].t == fa[x]) continue;
            if(2 * siz[e[i].t] > siz[x])
                ch[x][1] = e[i].t;
            else
                vu[x] += siz[e[i].t];
        }
        upd(x);
        ans += cal(x);
    }
    void access(int x, ll key) {
        splay(x);
        ans -= cal(x);//del the old contribution
        siz[x] += key; val[x] += key;
        if(R && 2 * siz[R] <= (siz[x] - siz[L])) {
            vu[x] += siz[R];//move to the vultr son
            R = 0;//del the old heavy son
        }
        ans += cal(x);//recal the contribution
        int son = x;
        while((x = fa[son])) {
            splay(x);
            ans -= cal(x);//del the old contribution
            siz[x] += key; vu[x] += key;
            if(R && 2 * siz[R] <= (siz[x] - siz[L])) {
                vu[x] += siz[R];//move to the vultr son
                R = 0;//del the old heavy son
            }
            if(2 * siz[son] > (siz[x] - siz[L])) {//try to update the heavy son by the kid
                vu[x] -= siz[son];//move to the heavy son
                R = son;//add the new heavy son
            }
            ans += cal(x);
            son = x;
        }
    }
}lct;

void addedge(int u, int v) {
    e[++ Etot] = {v, head[u]};
    head[u] = Etot;
}
int main() {
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i)
        lct.val[i] = read();
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read();
        addedge(u, v);
        addedge(v, u);
    }
    lct.dfs(1);
    printf("%lld\n", ans);
    
    while(m --) {
        int x = read(), y = read();
        lct.access(x, y);
        printf("%lld\n", ans);
    }
    return 0;
}
Last modification:March 15th, 2019 at 11:20 am

Leave a Comment