首页 > 代码库 > Codeforces 383C . Propagating tree【树状数组，dfs】
Codeforces 383C . Propagating tree【树状数组，dfs】
题目大意：
有一棵树，对这个树有两种操作：1：表示为（1 x val），在编号为x的节点上加上val，然后给x节点的每个儿子加上- val，再给每个儿子的儿子加上-（- val），一直加到没有儿子为止。2：表示为（2 x）查询x节点上的值。
做法：
由于每次修改操作修改的并不是一个值，而是很多值，那我们将该题抽象成区间修改，点查询的问题。那怎么抽象呢？可以明白的是，每次操作虽然有加有减，但是每次做加法操作，或者减法操作的都是同一部分数（也就是说，在某次加上同一个数的节点们，下次操作一定是加上或者减去相同的数），但是如果以树原来的编号为基础的话，那我们需要修改相同的数的那些节点肯定是不连续的，那就无法使用线段树或者树状数组的区间修改了。应该怎么办呢？我们考虑一下能不能将这树上的节点重新排序，使得每次修改的值在一个连续的区间。比如说有如下一棵树：
树的右边第一列代表深度，第二列代表着有着相同值（0或者1）的这些层的节点修改时都是同加或者同减的。比如第二层的节点和第四层的每个节点在修改时进行的操作一定是全是加，或者全是减，不可能一部分节点加，一部分节点减的。
那我们怎么将每次操作需要修改的值都重新编号为一个连续的区间呢？ 如上图我们应该是重新编号为这样的：
1 2 3 4 5678910 //新数组下标
1 4 5 6 7289310 //重新编号之后的数组
这样一来，我们就把每次需要修改的值变成了连续的了，比如说修改操作为(1 1 val)，那么我们需要加val的节点在新数组中的区间为[1,5]，需要减val的节点在[6,10]；如果修改操作为（1 2 val）那么我们需要加val的节点在新数组中的区间为[6,8]，需要减val的节点在[2,3]；
那具体怎么才能编号成这样呢？我们首先将每个节点对应的上图右边第二列的值存在d[]数组中，先从根节点（1）开始，跳层DFS，以dfs的顺序将遍历到的儿子节点一个个的加到新数组中。遍历完之后，再对根节点的每个儿子做一遍相同的操作即可。（具体可以看代码）
得到这个数组之后呢，我们还要预处理出对某个点进行修改操作，我们需要在那个区间加值，在哪个区间减值。也是用dfs，每个节点的属性可以由儿子来确定。具体看代码和注释：
代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 200020
using namespace std;
struct ee//存储需要修改哪些区间的结构体
{
int x1,y1,x2,y2;
}e[N];
vector<int> g[N];
int n,m,a[N],d[N],c[N],bef[N],index=1;
void dfs1(int x,int fa,int deep)//处理d[]数组
{
d[x]=deep;
for(int i=0;i<g[x].size();i++)
if(g[x][i]!=fa) dfs1(g[x][i],x,1-deep);
}
void dfs2(int x,int fa,int deep)//得到新数组
{
if(d[x]==deep) bef[x]=index++;//aft[index++]=x;//bef[i] 其中，i是原节点的编号，bef[i]是i在新数组中的下标
for(int i=0;i<g[x].size();i++)
if(g[x][i]!=fa) dfs2(g[x][i],x,deep);
}
void dfs3(int x,int fa)//预处理每个点的属性
{
for(int i=0;i<g[x].size();i++)
if(g[x][i]!=fa) dfs3(g[x][i],x);
int ma1=bef[x],mi2=N,ma2=0;
for(int i=0;i<g[x].size();i++)
{
if(g[x][i]==fa) continue;
int cur=g[x][i];
mi2=min(mi2,e[cur].x1);
ma2=max(ma2,e[cur].y1);
ma1=max(ma1,e[cur].y2);
}
e[x].x1=bef[x],e[x].y1=ma1,e[x].x2=mi2,e[x].y2=ma2;//[x1,y1]为需要加值操作的区间，[x2,y2]为需要减值操作的区间，可以由儿子确定
}
int getnum(int x)//下面便是树状数组的区间修改，点查询函数咯~
{
int rnt=0;
for(int i=x;i<=n;i+=(i&(-i)))
{
rnt+=c[i];
}
return rnt;
}
void add(int i,int a)
{
while(i>=1)
{
c[i]+=a;
i-=(i&(-i));
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=0;i<n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b),g[b].push_back(a);
}
dfs1(1,0,1);//计算d[]数组
dfs2(1,0,1);//对根节点进行处理
for(int i=0;i<g[1].size();i++)
dfs2(g[1][i],1,0);//对根节点的每个儿子进行处理
dfs3(1,0);//预处理
while(m--)
{
int ty;
scanf("%d",&ty);
if(ty==1)
{
int x,y;
scanf("%d%d",&x,&y);
int l1=e[x].x1,r1=e[x].y1,l2=e[x].x2,r2=e[x].y2;
add(r1,y),add(l1-1,-y);
if(r2!=0) add(r2,-y),add(l2-1,y);//如果不是根节点再进行减操作
}
else
{
int x;
scanf("%d",&x);
cout<<getnum(bef[x])+a[x]<<endl;
}
}
return 0;
}
Codeforces 383C . Propagating tree【树状数组，dfs】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。