1006 - 树上信息维护
dfs序
一棵树被 dfs 时所经过的节点的顺序。
一般的作用是维护子树信息，如果记录 dfn[i] 表示 i 号点的 dfs 序，sze[i] 表示 i 号点的子树大小
那么 x 是 y 的祖先等价于: dfn[y] ∈ [ dfn[x] , dfn[x] + sze[x] − 1]
树上操作：
- 单点加
- 单点求值
- 子树加
- 子树求和
- 链加
- 链求和
链加：将节点x到y最短路径上所有的点的权值+v
链求和：查询x到y的路径权值和
解法
（先声明：以下算法均是基于不会树链剖分的条件下进行，但这两种算法各有优劣，大家还是都学吧）
问题一：
有n个节点N-1条边，这是一颗树，有2个操作：
1 x y v：表示将节点x到y最短路径上所有的点的权值+v
2 x：表示查询节点x的权值
开始的时候每个节点的权值是0
这个问题就是一个简单的链加+单点查询
对于链加，我们可以将其看作一个点到根的路径加
说详细点就是：如图，假设我们现在要在节点x到y最短路径上所有的点的权值+v
我们就转化为在 x 到根的路径上加 v ，在 y 到根的路径上加 v，并且在 lca 到根的路径上减 v，再在 lca 的父亲到根的路径上减 v
单点查询的时候我们就查询这个点 x 的子树中所有的贡献，用数据结构对贡献进行维护
代码
这里我使用的是树状数组进行维护
#include<bits/stdc++.h>
#define in read()
#define N 200009
using namespace std;
inline int read(){
char ch;int res=0;
while((ch=getchar())<'0'||ch>'9');
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return res;
}
int n,q;
int nxt[N],head[N],to[N],cnt=0;
void add(int x,int y){ nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}
int fa[N][25],val[N],dep[N],dfn[N],num=0,sze[N];
void Dfs(int u,int fu){
sze[dfn[u]]=1;
for(int e=head[u];e;e=nxt[e]){
int v=to[e];
if(v==fu) continue;
dfn[v]=++num;
fa[v][0]=u;dep[v]=dep[u]+1;
Dfs(v,u);
sze[dfn[u]]+=sze[dfn[v]];
}
}
int getlca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=20;i>=0;--i){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int lowbits(int x) {return x&(-x);}
void modify(int pos,int v){
if(pos==0) return;
while(pos<=n){
val[pos]+=v;
pos+=lowbits(pos);
}
}
int query(int x){
int res=0;
while(x>0){
res+=val[x];
x-=lowbits(x);
}
return res;
}
int main(){
n=in;
int i,j,k;
for(i=1;i<n;++i){
int x=in;int y=in;
add(x,y);add(y,x);
}
dep[1]=1;dfn[num=1]=1;
Dfs(1,0);
q=in;
for(int j=1;j<=20;++j)
for(int i=1;i<=n;++i)
fa[i][j]=fa[fa[i][j-1]][j-1];
int c,x,y,v;
while(q--){
c=in;
if(c==1){
x=in;y=in;v=in;
modify(dfn[x],v);modify(dfn[y],v);
int lca=getlca(x,y);
modify(dfn[lca],-v);modify(dfn[fa[lca][0]],-v);
}
else{
x=in;
int l=dfn[x],r=dfn[x]+sze[dfn[x]]-1;
printf("%d\n",query(r)-query(l-1));
}
}
return 0;
}
问题二：
有n个节点N-1条边，这是一颗树，有2个操作：
1 x y v：表示将节点x到y最短路径上所有的点的权值+v
2 x：表示查询子树x的权值和
开始的时候每个节点的权值是0
这个问题就是一个上一个问题的小变：链加+子树求和
那么解法也就只是小变了一下
对于链加：一样的操作
子树求和时，考虑一个修改 （y，v）对节点 x 有影响，当且仅当这个节点 y 存在于 x 的子树中，又由于是链上修改，所以贡献就为:(dep[y] − dep[x] + 1) ∗ v
分离变量，即为 dep[y] ∗ v + ( 1 - dep[x] )∗ v。（（1-dep[x] ）是常数，可以提取出来，就只用统计 v ）
然后就变成单点加 dep[y] * v ，以及单点加 v ，由于这两个需要单独维护
所以我们需要维护两个树状数组，统计子树内的贡献
代码
#include<bits/stdc++.h>
#define in read()
#define N 200009
using namespace std;
inline int read(){
char ch;int res=0;
while((ch=getchar())<'0'||ch>'9');
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return res;
}
int n,q;
int nxt[N],head[N],to[N],cnt=0;
void add(int x,int y){ nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}
int fa[N][25],val[N],dep[N],dfn[N],num=0,sze[N],val2[N];
void Dfs(int u,int fu){
sze[dfn[u]]=1;
for(int e=head[u];e;e=nxt[e]){
int v=to[e];
if(v==fu) continue;
dfn[v]=++num;
fa[v][0]=u;dep[v]=dep[u]+1;
Dfs(v,u);
sze[dfn[u]]+=sze[dfn[v]];
}
}
int getlca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;--i) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=20;i>=0;--i)
if(fa[x][i]!=fa[y][i]){ x=fa[x][i]; y=fa[y][i];}
return fa[x][0];
}
int lowbits(int x) {return x&(-x);}
void modify(int pos,int v){
if(pos==0) return;
while(pos<=n){ val[pos]+=v;pos+=lowbits(pos);}
}
int query(int x){
int res=0;
while(x>0){res+=val[x];x-=lowbits(x);}
return res;
}
void modify2(int pos,int v){
if(pos==0) return;
while(pos<=n){ val2[pos]+=v;pos+=lowbits(pos);}
}
int query2(int x){
int res=0;
while(x>0){res+=val2[x];x-=lowbits(x);}
return res;
}
int main(){
n=in;
int i,j,k;
for(i=1;i<n;++i){
int x=in;int y=in;
add(x,y);add(y,x);
}
dep[1]=1;dfn[num=1]=1;
Dfs(1,0);
q=in;
for(int j=1;j<=20;++j)
for(int i=1;i<=n;++i)
fa[i][j]=fa[fa[i][j-1]][j-1];
int c,x,y,v;
while(q--){
c=in;
if(c==1){
x=in;y=in;v=in;
modify(dfn[x],v*dep[x]);modify(dfn[y],v*dep[y]);
modify2(dfn[x],v);modify2(dfn[y],v);
int lca=getlca(x,y);
modify(dfn[lca],-v*dep[lca]);modify(dfn[fa[lca][0]],-v*dep[fa[lca][0]]);
modify2(dfn[lca],-v);modify2(dfn[fa[lca][0]],-v);
}
else{
x=in;
int l=dfn[x],r=dfn[x]+sze[dfn[x]]-1;
printf("%d\n",query(r)-query(l-1)+(query2(r)-query2(l-1))*(1-dep[x]));
}
}
return 0;
}
问题三：
有n个节点N-1条边，这是一颗树，有2个操作：
1 x v：表示将节点x的权值+v
2 x y：表示查询x到y的路径权值和
这个问题就是一个：单点加+链求和
链求和依旧看作是点到根的路径和
那么考虑一个修改（y，v）对这条链的影响，当且仅当 y 是 x 的祖先
也就是说一个点 y 的修改，会影响以 y 为根的整颗子树，那么修改的时候就变成区间修改咯
最后链求和就是一个单点查询
相当于这道题转化过来就是：要求你写一个数据结构，支持区间修改，及单点查询
其实树状数组也是可以的，增加一个差分序列即可，只是这里我用的是线段树
代码
#include<bits/stdc++.h>
#define N 100009
#define in read()
#define lc (k<<1)
#define rc (k<<1)|1
using namespace std;
inline int read(){
char ch;int res=0;
while((ch=getchar())<'0'||ch>'9');
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return res;
}
int head[N],nxt[2*N],to[2*N],cnt=0;
void add(int x,int y){nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}
int n,val[N],d[4*N],q,fa[N][25];
int dfn[N],num=0,sze[N],dep[N];
int lzy[4*N];
void dfs(int u,int fu){
sze[dfn[u]]=1;
for(int e=head[u];e;e=nxt[e]){
int v=to[e];
if(v==fu) continue;
fa[v][0]=u;
dfn[v]=++num;dep[v]=dep[u]+1;
d[num]=d[dfn[u]]+val[v];
dfs(v,u);
sze[dfn[u]]+=sze[dfn[v]];
}
}
void pushdown(int k){
lzy[lc]+=lzy[k];
lzy[rc]+=lzy[k];
lzy[k]=0;
}
void modify(int k,int l,int r,int x,int y,int z){
if(x<=l&&r<=y){
lzy[k]+=z;
return;
}
if(lzy[k]) pushdown(k);
int mid=l+r>>1;
if(x<=mid) modify(lc,l,mid,x,y,z);
if(y>mid) modify(rc,mid+1,r,x,y,z);
}
int getlca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;--i)
if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=20;i>=0;--i){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int query(int k,int l,int r,int x){//查询第x个节点的值
if(x==0) return 0;
int mid=l+r>>1;
if(l==r&&l==x){
return d[x]+lzy[k];
}
if(lzy[k]) pushdown(k);
if(x<=mid) return query(lc,l,mid,x);
else return query(rc,mid+1,r,x);
}
int main(){
n=in;
int i,j,k;
for(i=1;i<=n;++i) val[i]=in;
for(i=1;i<n;++i){
int u=in,v=in;
add(u,v);add(v,u);
}
dfn[num=1]=1;d[1]=val[1];dep[1]=1;
dfs(1,0);
for(int j=1;j<=20;++j)
for(int i=1;i<=n;++i)
fa[i][j]=fa[fa[i][j-1]][j-1];
q=in;
int type,x,y;
while(q--){
type=in;x=in;y=in;
if(type==1) modify(1,1,n,dfn[x],dfn[x]+sze[dfn[x]]-1,y);
//是用dfn[x]存的sze！！！
else{
int lca=getlca(x,y);
int hh=query(1,1,n,dfn[x]);
int hh1=query(1,1,n,dfn[y]);
printf("%d\n",hh+hh1-query(1,1,n,dfn[lca])-query(1,1,n,dfn[fa[lca][0]]));
}
}
return 0;
}
问题四：
维护一棵树，支持：子树加，链加，链求和。
这两个修改得分开处理
子树加对于链求和：
对于一颗子树的修改（x，v），能被它影响的就只有它的子树，所以当链的一个端点 y ，在以 x 为根的子树中时，这个修改对它的影响就是：（dep[y] - dep[x] + 1）* v
同样的，分离常数：（dep[y] + 1）* v - dep[x] * v
再用两个树状数组什么的维护就好啦
链加对于链求和：
这个就需要分情况讨论了
若 x 为 y 的祖先，那么贡献为 dep[x] ∗ v。
若 y 为 x 的祖先，那么贡献为 dep[y] ∗ v。
分开维护贡献即可。
具体一点就是说：
对于一个修改我们用一个数据结构来处理其子树区间加dep[x]*v
再用一个来处理自己加v，这分别对应着上面两种情况
查询的时候在第一个数据结构中进行单点查询
在第二个数据结构中进行子树区间求和，这个值还要乘以dep[root]
代码
大家自己敲吧，有了上面三个样本过后应该还是很好敲出来的了