CF383C Propagating tree解题报告

解题报告

CF383C Propagating tree解题报告：

更好的阅读体验

题意

题意：给你一颗$n$个结点带点权的树，支持两个操作：①把某个点权值加$x$，它的所有儿子权值加$-x$，它所有儿子的儿子权值加$-(-x)$……②求某点权值
数据范围：$1\leqslant n\leqslant 2\cdot 10^5$。

分析

这是一道比较好的dfn序练习题。

dfn序，即某个点在dfs时第一次遍历的时间戳，有一个很优秀的性质：某个点的子树（包括它自己）中所有点的dfn序恰好是一段连续的序列。这个性质很显然，用dfs的搜索顺序想就很容易理解了。

看到这道题，我们发现它的修改都是关于子树的，所以我们可以想到用dfn序把树拍平成序列来维护。

但是它还有一个问题，如何让它的子树间断地加减权值呢？其实这也很简单，这个操作等价于这个点所有$0$级儿子加，所有$1$级儿子减，所有$2$级儿子加……因为dfs的顺序，所以我们可以知道dfn序的另一个性质——若两个点层数奇偶性不同，那么它们的dfn序奇偶性也不同。

这样就好办了，由于是区间修改，单点查询，所以可以建两个树状数组，一个维护奇数层次，一个维护偶数层次，然后修改差分一下，查询直接求就可以了。

代码

#include<stdio.h>
#define lowbit(x) x&-x
const int maxn=200005,maxm=400005,maxt=400005;
int i,j,k,m,n,e,cnt;
int start[maxn],to[maxm],then[maxm],sum[maxt][2],dfn[maxn],end[maxn],tp[maxn],a[maxn];
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void update(int x,int v,int t){
    for(int i=x;i<maxt;i+=lowbit(i))
        sum[i][t]+=v;
}
int query(int x,int t){
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=sum[i][t];
    return res;
}
void dfs(int x,int last,int t){
    dfn[x]=++cnt,tp[x]=t;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x,t^1);
    }
    end[x]=cnt;
}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0,0);
    for(i=1;i<=m;i++){
        int opt,x,v;
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d",&x,&v);
            update(dfn[x],v,tp[x]);
            update(end[x]+1,-v,tp[x]);
        }
        if(opt==2){
            scanf("%d",&x);
            printf("%d\n",a[x]+query(dfn[x],tp[x])-query(dfn[x],tp[x]^1));
        }
    }
    return 0;
}