对于一棵树，我们可以通过深度优先搜索记录到达每一个点的时间戳，由这个时间戳构成的序列就是dfs序，每个时间戳代表一个节点。
我们可以通过以下代码实现： void dfs(int u) { st[u]=++tot;//记录子树开始的访问时间 for(int re i=f[u];i;i=nxp[i]) { int v=e[i].v; if(!st[v]) { dep[v]=dep[u]+1; dfs(v) }; } ed[u]=tot;//记录子树访问结束的时间 } 对于这样的dfs序，我们就能利用树状数组进行维护单点信息，修改单点，维护子树信息，修改子树，维护路径，修改路径等操作。（如果涉及复杂路径修改或一些复杂的信息维护，最好使用树链剖分与线段树实现）

问题一：单点修改，子树查询

对于这样的问题，我们只需要直接用树状数组进行单点修改，通过树状数组求得区间[st[root]-1,ed[root]]即可求得以root为根的子树和。
例题大意：
给出一个苹果树，每个节点一开始都有苹果 C X，如果X点有苹果，则拿掉，如果没有，则新长出一个 Q X，查询X点与它的所有后代分支一共有几个苹果 #include #include #include #include #include #include #include #define re register using namespace std; int n,m,a,b,s,t; const int N=2e5+1; int f[N]; int c[N]; int g[N]; int nxp[N<<2|1]; int cnt=0,tot=0; struct ndeo{ int u,v; }e[N]; int idx=0; inline void add(int u,int v) { e[++cnt].u=u; e[cnt].v=v; nxp[cnt]=f[u]; f[u]=cnt; } inline int low(int x){return x&(-x);} inline void change(int k,int v) { while(k<=idx) { c[k]+=v; k+=low(k); } } inline int ask(int k) { int ret=0; while(k>0) { ret+=c[k]; k-=low(k); } return ret; } int st[N]; int ed[N]; void dfs(int u) { st[u]=++idx; for(int re i=f[u];i;i=nxp[i]) { int v=e[i].v; if(!st[v])dfs(v); } ed[u]=idx; } char p; int main() { scanf("%d",&n); for(int re i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); g[i]=1; } g[n]=1; scanf("%d",&m); dfs(1); for(int re i=1;i<=n;i++) change(st[i],1); for(int re i=1;i<=m;i++) { scanf(" %c%d",&p,&a); if(p=='C') { if(g[a])change(st[a],-1); else change(st[a],1); g[a]^=1; } else printf("%d ",ask(ed[a])-ask(st[a]-1)); } }

问题二：树上路径修改，单点查询

对于这么一个题，我们可以利用树上差分的思想：
修改x->y的路径，就等价于
x->root +v;
y->root +v;
lca(x,y)->root -v;
fa[lca(x,y)]->root -v;
于是问题的修改又可以转换为单点修改。而对于一个节点y的权值，其它节点会对其产生影响，当且仅当其它节点在y的子树内。若y不受x的路径影响，y子树中必有一部分节点+v,一部分节点-v，则对y没有影响。若y受x的路径影响，则y中的子树和就会增大v。这一点可以画图举例理解。所以我们可以维护子树和，修改单点，就能解决这个问题。
例题大意：
有n个节点N-1条边，这是一颗树，有2个操作：
1 x y v：表示将节点x到y最短路径上所有的点的权值+v
2 x：表示查询节点x的权值
开始的时候每个节点的权值是0 #include #include #include #include #include #include #include #define re register using namespace std; int n,m,a,b,s,t; const int N=2e5+1; int f[N]; int c[N]; int g[N]; int nxp[N<<2|1]; int cnt=0,tot=0; struct ndeo{ int u,v; }e[N]; int idx=0; inline void add(int u,int v) { e[++cnt].u=u; e[cnt].v=v; nxp[cnt]=f[u]; f[u]=cnt; } inline int low(int x){return x&(-x);} inline void change(int k,int v) { while(k<=idx) { c[k]+=v; k+=low(k); } } inline int ask(int k) { int ret=0; while(k>0) { ret+=c[k]; k-=low(k); } return ret; } int fa[N][20]; int st[N]; int ed[N]; int dep[N]; void dfs(int u) { st[u]=++idx; for(int re i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int re i=f[u];i;i=nxp[i]) { int v=e[i].v; if(!dep[v]) { dep[v]=dep[u]+1; fa[v][0]=u; dfs(v); } } ed[u]=idx; } int lca(int a,int b) { if(dep[a]<dep[b])swap(a,b); int t=dep[a]-dep[b]; for(int re i=0;(1<<i)<=t;i++) if(t&(1<<i))a=fa[a][i]; if(a==b)return a; for(int re i=18;i>=0;i--) { if(fa[a][i]!=fa[b][i]) { a=fa[a][i]; b=fa[b][i]; } } return fa[a][0]; } char p; int main() { scanf("%d",&n); for(int re i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b);add(b,a); } scanf("%d",&m); dep[1]=1; dfs(1); for(int re i=1;i<=m;i++) { int q,z; scanf("%d",&q); if(q==1) { scanf("%d%d%d",&a,&b,&z); int lc=lca(a,b); change(st[a],z); change(st[b],z); change(st[lc],-z); if(lc!=1) change(st[fa[lc][0]],-z); } else { scanf("%d",&a); printf("%d ",ask(ed[a])-ask(st[a]-1)); } } }

问题三：树上路径修改，子树查询

我们考虑假设X在Y的子树内，那么对于询问点Y，询问值会加
上W[x] * (depth[x] - depth[y]+ 1)。
故整颗子树所受影响即：
$sum_{x在y子树内}{w[x]*(dep[x]-dep[y]+1)}$
拆开可以得到：
$sum_{x在y子树内}{w[x]*(dep[x]+1)}-dep[y]*sum_{x在y子树内} {w[x]}$
对于每一次修改，我们是可以知道x的，因此我们可以维护两个值w[x]和w[x]*(dep[x]+1)的子树和，询问时再处理回答即可。
例题大意：
有n个节点N-1条边，这是一颗树，有2个操作：
1 x y v：表示将节点x到y最短路径上所有的点的权值+v
2 x：表示查询子树x的权值和
开始的时候每个节点的权值是0
代码： #include #include #include #include #include #include #include #define re register using namespace std; int n,m,a,b,s,t; const int N=2e5+1; int f[N]; int g[N]; int nxp[N<<2|1]; int cnt=0,tot=0; struct ndeo{ int u,v; }e[N]; int idx=0; inline int low(int x){return x&(-x);} struct tree{ int c[N]; inline void change(int k,int v) { while(k<=idx) { c[k]+=v; k+=low(k); } } inline int ask(int k) { int ret=0; while(k>0) { ret+=c[k]; k-=low(k); } return ret; } }t1,t2;//t1:w,t2:(dep(x)+1)*w inline void add(int u,int v) { e[++cnt].u=u; e[cnt].v=v; nxp[cnt]=f[u]; f[u]=cnt; } int fa[N][20]; int st[N]; int ed[N]; int dep[N]; void dfs(int u) { st[u]=++idx; for(int re i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int re i=f[u];i;i=nxp[i]) { int v=e[i].v; if(!dep[v]) { dep[v]=dep[u]+1; fa