题解 P11855 [CSP-J2022 山东] 部署

前排提醒，本题解做法涉及以下知识点：

【4】深度优先遍历（入门）
【8】离线处理思想（NOI）（别怕，没那么难）

致管理：把时间算错了……只把“花絮”部分的“三年”改为“两年”，其他地方均未改动。

题意

给定一棵以

1

号点为根的树，初始时每个点有点权

a_i

，维护

m

次操作，操作包括两种：

1 x y：将以 $x$ 为根的子树的所有点点权加 $y$ 。
2 x y：将 $x$ 及与之有边直接相连的所有点点权加 $y$ 。

操作完后进行

q

次询问，每次指定一个点，询问其点权。

数据范围

1\le n,m,q\le 10^6,1\le a_i\le 10^9,1\le y\le 10

。

思路

给的两种操作看上去不好下手，但是此题有一个令人注意的点：一般的题都是操作同时包括修改和查询，但本题中是修改完了再查询，这个时候就需要离线处理思想发挥作用了。所谓离线处理思想，就是在操作的时候不直接操作上去，而是把操作先记录下来，等到合适的时机（通常是用到的时候）再操作以优化复杂度。

读完这段话之后，如果你之前没有想到，建议先从这个入手继续思考一下，问题应该会简单很多。

这道题直接按照上面的说法做就可以了。开两个数组分别记录每个点

1

操作

y

值的和以及

2

操作

y

值的和。所有操作结束之后遍历整棵树，遍历到一个点时：

对于其记录的 $1$ 操作，修改当前点的点权并将 $y$ 值转移到它的所有儿子节点。
对于其记录的 $2$ 操作，修改相关点的点权。

这样由于每条边最多会被遍历

3

次（该边的两个端点中，深度较小的点的两种操作均会遍历该边，深度较大的点的

2

操作遍历该边），故时间复杂度为

\text{O}(n)

，然后直接回答询问即可。

代码

直接放上~~落满了灰的~~赛时代码，由于挺好写的，故没有注释。

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,q,u,v,op,x,y,a[1000010],tag1[1000010],tag2[1000010],fa[1000010];
vector<ll> g[1000010];
void change(ll now){
	for(int i=0;i<g[now].size();i++){
		if(g[now][i]!=fa[now]){
			fa[g[now][i]]=now;
			change(g[now][i]);
		}
	}
}
void pushdown(ll now){
	a[now]+=tag1[now];
	a[now]+=tag2[now];
	for(int i=0;i<g[now].size();i++){
		a[g[now][i]]+=tag2[now];
		if(g[now][i]!=fa[now]){
			tag1[g[now][i]]+=tag1[now];
			pushdown(g[now][i]);
		}
	} 
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n-1;i++){
		cin>>u>>v;
		u--;v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	fa[0]=0;
	change(0);
	cin>>m;
	while(m--){
		cin>>op>>x>>y;
		if(op==1)tag1[x-1]+=y;
		else tag2[x-1]+=y;
	}
	pushdown(0);
	cin>>q;
	while(q--){
		cin>>x;
		cout<<a[x-1]<<endl;
	} 
	return 0;
}

花絮

洛谷终于搬题了！

喜报：成功于近两年前准确预测了洛谷评定的题目难度。

本人场上获得了

290

分的好成绩，挂了

30

分，原因至今不明，合理怀疑是机子太慢了，因为我的 T3 在洛谷上怎么测都是

100

但官方测的是

70

……

直观感受本套题目：

T1 差分板子秒了，唯一的坑点是下标。
T2 原题 CF1730B，场上瞎搞 1h 多点过了（其实好卡）。
T3（本题）还不错，就是这玩意好像涉及【8】离线处理思想吧……
T4 原题 ARC058C，状压 DP 放普及几个意思？？！
X 组更加劲爆，直接两道 P 字头原题（T1 原题 P1007 独木桥，T3 原题 P1638 逛画展不过通胀了）。

题解 P11855 [CSP-J2022 山东] 部署

文章操作

题解 P11855 [CSP-J2022 山东] 部署

题意

思路

代码

花絮

相关推荐

评论

题解 P11855 [CSP-J2022 山东] 部署