自动搬运

查看原文

来自洛谷，原作者为

	JuRuoOIer CSP-S2024 打炸并被卡勾七线的初中牲

搬运于2025-08-24 23:10:50，当前版本为作者最后更新于2025-03-05 22:23:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 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)$，然后直接回答询问即可。

代码

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

#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 逛画展 不过通胀了）。