CF1797D

DDF_ · 2025-11-23 21:35:04 · 题解

Accepted。

题解

他提到重儿子，所以不要树链剖分。令 son_{x} 为 x 的重儿子，fa_{x} 为 x 的父节点。

对于操作 1，dfs 一遍预处理一个数组 s 存以 x 为根的子树重要度和。

对于操作 2，发现其只会影响 x，son_{x}，fa_{x}，所以只需要操作 3 个点，考虑动态维护节点 x 的儿子。

操作 2 的具体过程其实是：son_{x} 变为 fa_{x} 的儿子之一，x 变为 son_{x} 的儿子之一。

然后就是对 s_x 和 siz_{x} 进行修改。

其中 s_{x}' = s_{x} - s_{son_{x}}，s_{son_{x}}'= s_{x}，siz_{x} 同理。

此时 x，son_{x}，fa_{x} 的儿子都会发生变化。

在 x 的儿子中删去 son_{x}，在 son_{x} 的儿子中删去 x，在 fa_{x} 的儿子中删去 x 并添加 son_{x}，这用一个 set 便可以解决（set 的排序功能还可以帮助找 son_{x}）。

STL 很神奇吧！

此题结。

代码

#include<bits/stdc++.h>
#define pii pair<int,int> 
#define ll long long
using namespace std;
const int N=1e5+5;
int n,m;
int head[N],to[2*N],nxt[2*N],idx;
int siz[N],fa[N];
ll s[N],a[N];
set<pii> son[N];
inline void add(int x,int y) {
    nxt[++idx]=head[x],head[x]=idx,to[idx]=y;
    return;
}
void dfs(int x) {
    siz[x]=1,s[x]=a[x];
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if(y!=fa[x]) {
            fa[y]=x;
            dfs(y);
            siz[x]+=siz[y],s[x]+=s[y];
            son[x].insert({-siz[y],y});
        }
    }
    return;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1);
    while(m--) {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1) printf("%lld\n",s[x]);
        if(op==2) {
            if(son[x].empty()) continue;
            int hv=(*son[x].begin()).second;
            son[fa[x]].erase(son[fa[x]].find({-siz[x],x}));
            s[x]-=s[hv],s[hv]+=s[x];
            siz[x]-=siz[hv],siz[hv]+=siz[x];
            son[hv].insert({-siz[x],x});
            son[fa[x]].insert({-siz[hv],hv});
            son[x].erase(son[x].begin());
            fa[hv]=fa[x],fa[x]=hv;
        }
    }
    return 0;
}