[CSP-J 2022 山东] 部署

知识点

树上差分、离线处理、树的遍历

解题思路

所有查询在命令之后，可以离线处理。先迭代遍历树得到父亲及父先于子的顺序。命令1 x y只在sub[x]累加，最终沿父到子传播。命令2把y直接加到x与其父亲的direct中，同时在near[x]累加，代表给x的所有孩子的延迟增量。最终节点u的答案为初始值+沿祖先累积的sub[u]+direct[u]+near[parent[u]]。根的父亲为哨兵0。

正确性说明

子树命令对u生效当且仅当命令起点为u的祖先或u，故父到子累加sub恰好收齐。邻居命令分别贡献给起点、父亲、所有孩子，三个集合互不重叠；前两者直接记录，第三者由每个孩子读取父亲的near得到。所有更新线性叠加，最终公式正确。

易错点

操作2只影响一层，near不能像sub传播到所有后代；根没有父亲；百万深链不能递归DFS；用64位维护增量。

复杂度

时间O(n+m+q)，空间O(n)；邻接表与父序遍历均为迭代。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<long long>a(n+1),sub(n+1),direct(n+1),near(n+1);for(int i=1;i<=n;i++)cin>>a[i];vector<vector<int>>g(n+1);for(int i=1,u,v;i<n;i++){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}vector<int>pa(n+1),order;order.reserve(n);order.push_back(1);for(int i=0;i<(int)order.size();i++){int u=order[i];for(int v:g[u])if(v!=pa[u])pa[v]=u,order.push_back(v);}int m;cin>>m;while(m--){int p,x;long long y;cin>>p>>x>>y;if(p==1)sub[x]+=y;else{direct[x]+=y;if(pa[x])direct[pa[x]]+=y;near[x]+=y;}}for(int u:order){if(pa[u])sub[u]+=sub[pa[u]];a[u]+=sub[u]+direct[u]+near[pa[u]];}int q;cin>>q;while(q--){int x;cin>>x;cout<<a[x]<<'\n';}}