专栏文章

CF1797D

DDDF_
CF1797D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1zdie
此快照首次捕获于
2025/12/01 19:15
3 个月前
此快照最后确认于
2025/12/01 19:15
3 个月前
查看原文
Accepted。

题解

他提到重儿子，所以不要树链剖分。令 sonxson_{x} 为 xx 的重儿子，faxfa_{x} 为 xx 的父节点。
对于操作 1，dfs 一遍预处理一个数组 ss 存以 xx 为根的子树重要度和。
对于操作 2，发现其只会影响 xx，sonxson_{x}，faxfa_{x}，所以只需要操作 33 个点，考虑动态维护节点 xx 的儿子。
操作 2 的具体过程其实是：sonxson_{x} 变为 faxfa_{x} 的儿子之一，xx 变为 sonxson_{x} 的儿子之一。
然后就是对 sxs_x 和 sizxsiz_{x} 进行修改。
其中 sx′=sx−ssonxs_{x}' = s_{x} - s_{son_{x}}，ssonx′=sxs_{son_{x}}'= s_{x}，sizxsiz_{x} 同理。
此时 xx，sonxson_{x}，faxfa_{x} 的儿子都会发生变化。
在 xx 的儿子中删去 sonxson_{x}，在 sonxson_{x} 的儿子中删去 xx，在 faxfa_{x} 的儿子中删去 xx 并添加 sonxson_{x}，这用一个 set 便可以解决（set 的排序功能还可以帮助找 sonxson_{x}）。
STL 很神奇吧！
此题结。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...