题解 CF383C 【Propagating tree】

SSerxhs · 2019-04-19 17:51:13 · 题解

为什么要用线段树这种大常数的呢...没有区间询问，树状数组就好了啊

考虑维护一个数组f[n]，表示第n号节点的修改情况，其中如果dep[n]是奇数则记录增加量，否则记录减少量。则题中修改就等同于在dfs序上修改一段区间（因为这时候增减已经不影响了），差分树状数组即可。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=2e5+2,M=4e5+2;
int a[N],lj[M],nxt[M],fir[N],f[N],dfn[N],siz[N],v[N],dep[N];
int n,m,i,j,x,y,c,bs,z;
inline void read(int &x)
{
    c=getchar();
    while ((c<48)||(c>57)) c=getchar();
    x=c^48;c=getchar();
    while ((c>=48)&&(c<=57))
    {
        x=x*10+(c^48);
        c=getchar();
    }
}
void dfs(int x)
{
    siz[x]=1;dfn[x]=++bs;
    for (int i=fir[x];i;i=nxt[i]) if (lj[i]!=f[x])
    {
        dep[lj[i]]=dep[f[lj[i]]=x]+1;dfs(lj[i]);siz[x]+=siz[lj[i]];
    }
}
inline void add(register int x,register int y,register int z)
{
    while (x<=n) {a[x]+=z;x+=x&(-x);}++y;
    while (y<=n) {a[y]-=z;y+=y&(-y);}
}
inline int sum(register int x)
{
    register int r=0;
    while (x) {r+=a[x];x^=x&(-x);}
    return r;
}
int main()
{
    read(n);read(m);
    for (i=1;i<=n;i++) read(v[i]);
    for (i=1;i<n;i++)
    {
        read(x);read(y);
        lj[++bs]=y;
        nxt[bs]=fir[x];
        fir[x]=bs;
        lj[++bs]=x;
        nxt[bs]=fir[y];
        fir[y]=bs;
    }bs=0;
    dfs(1);
    while (m--)
    {
        read(y);read(x);
        if (y==1)
        {
            read(z);
            if (dep[x]&1) add(dfn[x],dfn[x]+siz[x]-1,z); else add(dfn[x],dfn[x]+siz[x]-1,-z);
        }
        else {z=sum(dfn[x]);if (dep[x]&1) printf("%d\n",v[x]+z); else printf("%d\n",v[x]-z);}
    }
}