前言
大佬们都说是经典题型，但对我这种小白来说，这题确实挺难挺不错的，思考了好久才差不多弄明白。
下面我会详细的讲解一下。
题目链接
https://ac.nowcoder.com/acm/contest/5158/I
题目大意
一棵树，n个节点，m次操作，k为根节点；
输入n个正整数，表示第i个数的权值；
输入n-1对数，为节点，表示两者之间有边；
输入m个组数，每组代表一次操作：
1 node add ：表示将节点 node 的权值加上 add //加数
2 node ：表示求 node 节点的子树上所有节点的和（包括 node 节点本身） //输出
解题思路
我没想出是这个方法。
我的错误思路：
我当时的错误方法是记忆化搜索，用father[i]表示第i个节点的父亲，再用sum数组去存储子树和。通过每次更新数值都要记忆化搜索一次，更新路径上的sum值。输出sum值。
但是相当于每次更新都要dfs一次，本身dfs一次的递归次数就很多，还要每次更新都dfs一次，必然TLE。
因此，这方法不可行。
大佬的正确思路：
dfs序+树状数组
不知道大家是否听说过这两个东西，我没听说过dfs序，听说过树状数组，仅限听说，听雨巨说。
给大家先讲讲dfs序和树状数组（了解的可以忽略）
dfs序（基础讲解）
树状数组
要说为什么能想到，我感觉如果我知道dfs序与树状数组的搭配用法，我应该也能想到这种方法，毕竟挺经典的而且挺基础的，但是能不能成功实现另说了QWQ
AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int n,m,k;
int Time=0;
int a[N];
ll c[N];
int in[N],out[N];
vector<int> node[N];
//树状数组板子函数
int lowbit(int x){
return x&(-x);
}
void update(int x,int add){
while(x<=n){
c[x]+=add;
x+=lowbit(x);
}
}
ll getsum(int x){
ll ans=0LL;
while(x>0){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
//几乎是dfs序板子函数，一点变化下面讲解
void dfs(int x,int fa){
in[x]=++Time;
update(Time,a[x]);
for(int i=0;i<node[x].size();i++){
if(fa!=node[x][i]) dfs(node[x][i],x);
}
out[x]=Time;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
//简单的输入存储
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
node[u].push_back(v);
node[v].push_back(u);
}
//简单的存边
dfs(k,0);
//
for(int i=1;i<=m;i++){
int op,p,add;
cin>>op;
if(op==1){//add
cin>>p>>add;
update(in[p],add);
}
else{//print
cin>>p;
cout<<getsum(out[p])-getsum(in[p]-1)<<endl;
}
}
} 代码讲解
注意1：树状数组的函数中操作的下标不再是节点序序号（链接中树状数组代码讲解中是节点序序号），而是dfs序序号。
因此，update的作用是将dfs序序号为x的节点对应的树状数组c中的值加上add；getsum的作用是求前缀和，根据dfs序排序的前缀和，并非子树和，如图
上面一行是dfs序序号，下面是对应的节点序序号
若getsum(4)，则得到的结果为5+8+2+1=16；getsum(1)，得到的结果为5。（getsum函数的内部实现是通过累加c数组的值算得的）
注意2：update中不要更新a数组的值，因为在dfs函数中update的参数为a[x]，若a数组值发生改变，会影响c数组的赋值。
注意3：dfs中的update函数的目的是将包含dfs序序号为Time（其实Time本身就是在记录dfs序序号）节点的所有节点的c数组的值加上a[节点序序号]，因为此时c数组全零，此时相当于初始化。
注意4：op==1后执行的update函数的参数为in[p]，因为p为节点序序号，in[p]为p对应的dfs序序号，一切操作基于dfs序！
注意5：输出的时候，前缀和思想，in[p]需减一，求出dfs序序号从in[p]~out[p]的和，即以节点序序号为p的点为根节点子树的权值和。
总结
涨知识，第一次做树状数组的题就这么难，不过这样也算是彻底把树状数组的入门知识学明白了，花了一下午写的题解根本不亏！
实现起来还是挺难的！
现在重点是理解dfs序和树状数组的过程实现，从而更好的记住函数代码。
（其实这个题，我拉了4天的战线才学完的……引以为戒吧，借口：期末！理由充分！）
最后的最后，我还想问上天一句：我什么时候才能成为大佬啊啊啊！！！
京公网安备 11010502036488号