思路
每次操作都 DFS 一遍树，时间复杂度 \(O(nm)\)。期望得分 \(30\) pts。
但我们发现增兵是可以叠加的，那我们记录每个点 1、2 操作总共增了多少兵，最后离线 DFS 一遍即可，时间复杂度 \(O(n)\)。期望得分 \(100\) pts。
考虑强制在线怎么做：注意到 \(u\) 的子树的 DFS 序为从 \(u\) 开始连续子树大小个点，与 \(u\) 直接相连的点的 BFS 序即从 \(u\) 开始连续儿子数量个点再加上父节点。预处理出每个结点的 DFS 序、BFS 序和父结点，开两个线段树分别维护两个序，操作 2 再单点修改父结点即可。每次查询返回两个树上单点的和。时间复杂度 \(O(n+(m+q)\log n)\)，线段树常数过大，期望得分 \(80\) pts，而题目只需单点查询，所以可以使用树状数组维护。
实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,q;
int a[N],h[N],tot;
int b1[N],b2[N],ans[N];
struct Node{int to,nxt;
}e[2*N];
void Add(int u,int v){tot++;e[tot].to=v;e[tot].nxt=h[u];h[u]=tot;
}
void dfs(int u,int fa,int p){ans[u]+=p+b2[u];ans[fa]+=b2[u];for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(v==fa) continue;dfs(v,u,p+b1[v]);ans[v]+=b2[u];}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;Add(u,v),Add(v,u);}cin>>m;for(int i=1;i<=m;i++){int op,x,y;cin>>op>>x>>y;if(op==1) b1[x]+=y;else b2[x]+=y;}dfs(1,0,b1[1]);cin>>q;for(int i=1;i<=q;i++){int x;cin>>x;cout<<ans[x]+a[x]<<'\n';}return 0;
}