Path Queries
时间限制: 2000\ \mathrm{ms}
空间限制: 262144\ \mathrm{KB}
题目描述
给定一棵有根树，包含 n 个节点。节点编号为 1 到 n，节点 1 为根节点。每个节点都有一个值。
您的任务是处理以下类型的查询：
- 将节点 s 的值更改为 x。
- 计算从根到节点 s 的路径上的值的总和。
输入格式
第一个输入行包含两个整数 n 和 q：节点和查询的数量。节点编号为 1，2，\cdots，n。
下一行有 n 个整数 v_1,v_2,\cdots,v_n：每个节点的值。
然后有 n−1 条线描述边缘。每一行包含两个整数 a 和 b：节点 a 和 b 之间有一条边。
最后，有 q 行描述查询。每个查询的格式为 1 s x或 2 s。
计算从根到节点 s 的路径上的值的总和。
输出格式
对于类型 2 的查询，请输出结果。
样例
Input1
5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4
Output1
11
8
数据范围
1≤n,q≤2\times 10^5。
1≤a,b,s≤n。
1≤v_i,x≤10^9。
我的代码
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
#define i_will signed
#define ak main
#define IMO ()
#define int long long
I AK IOI;
const int MAXN=2e5+5;
vector<int>adj[MAXN];
int values[MAXN],sum[MAXN],parent[MAXN],n,q;
void dfs(int node,int par){
parent[node]=par;
sum[node]=values[node];
if(par!=-1)sum[node]+=sum[par];
for(int child:adj[node])if(child!=par)dfs(child,node);
}
void update(int s,int x){
if(values[s]==x)return;
int diff=x-values[s];
values[s]=x;
while(s!=-1){
sum[s]+=diff;
s=parent[s];
}
}
int query(int s){
return sum[s];
}
i_will ak IMO{
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>values[i];
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,-1);
for(int i=0;i<q;i++){
int type,s;
cin>>type>>s;
if(type==1){
int x;
cin>>x;
update(s,x);
}
else cout<<query(s)<<endl;
}
i_ak ioi;
}
样例不过。