P3178 [HAOI2015]树上操作

· · 题解

虽然树剖可以做,但用线段树/树状数组维护DFS序显然是个更简单的方法.

题目要求单点/子树加,到根求和,可以考虑直接维护每个点到根的权值和,每次查询也就成了单点查询.

接着来考虑每种修改产生的贡献:

  1. 单点修改:

很容易想到,增加一个点的权值后,它的子树内的所有节点到根的权值和会增加相应的值(因为必须经过当前点).

也就是说,若给点x增加一个权值z,就相当于给以x为根的子树内的所有节点增加z.

  1. 子树修改:

既然单点修改被变成了修改整个子树,子树修改就容易让人不知所措.

但其实还是用相同的方法,计算此次修改对每个点的权值的贡献即可.

假设给以x为根的子树增加z,那么对于子树中的一个节点y,产生的贡献相当于y到x路径上的所有节点单点加产生的贡献.由前面的推导可以推知,总贡献为(deep[y]-deep[x]+1)*z.(deep表深度)

应对每个节点修改的量已经知道了,但如果直接套用那个式子只能一个个地加,所以将其变形成为(deep[y]+1)z-deep[x]z.线段树中每个节点的深度和是很好处理的,但是由于此次修改计算方式不一样,所以要写两个修改和标记.

关于树的DFS序相关的技巧我就不多讲了,不会的看看代码也应该很容易理解.

下面放代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,m,dfn[100005],d[100005],tot,cnt,h[100005],ed[100005],st[100005],de[100005],ds[4000005];
struct ll
{
    long long nx;
    long long to;
}a[200005];
struct xds
{
    long long l,r;
    long long s;
    long long bj,bj1;
}t[4000005];
void ad(long long x,long long y)
{
    a[++cnt].nx=h[x];
    a[cnt].to=y;
    h[x]=cnt;
}
void dfs(long long x,long long fa)//处理DFS序和深度
{
    long long i,j;
    dfn[++tot]=x;
    st[x]=tot;//表示以子树x在DFS序中的开头处
    for(i=h[x];i;i=a[i].nx)
    {
        j=a[i].to;
        if(j==fa)
        continue;
        de[j]=de[x]+1;
        dfs(j,x);
    }
    ed[x]=tot;//子树x在DFS序中的结尾处
}
void up(long long v){t[v].s=t[v<<1].s+t[v<<1|1].s;}
void down(long long v)
{
    if(t[v].bj)//标准的加标记
    {
        t[v<<1].s+=t[v].bj*(t[v<<1].r-t[v<<1].l+1);
        t[v<<1|1].s+=t[v].bj*(t[v<<1|1].r-t[v<<1|1].l+1);
        t[v<<1].bj+=t[v].bj;
        t[v<<1|1].bj+=t[v].bj;
        t[v].bj=0;
    }
    if(t[v].bj1)//与加标记不同的是还要乘上一个深度和
    {
        t[v<<1].s+=(ds[v<<1]+1)*t[v].bj1*(t[v<<1].r-t[v<<1].l+1);
        t[v<<1|1].s+=(ds[v<<1|1]+1)*t[v].bj1*(t[v<<1|1].r-t[v<<1|1].l+1);
        t[v<<1].bj1+=t[v].bj1;
        t[v<<1|1].bj1+=t[v].bj1;
        t[v].bj1=0;
    }//ds数组表示线段树一个区间的深度和
}
void bd(long long v,long long l,long long r)
{
    long long mid;
    t[v].l=l;
    t[v].r=r;
    if(l==r)
    {
        ds[v]=de[dfn[l]];
        return ;
    }
    mid=l+r>>1;
    bd(v<<1,l,mid);
    bd(v<<1|1,mid+1,r);
    up(v);
    ds[v]=ds[v<<1]+ds[v<<1|1];//建树的时候同时处理
}
void xg(long long v,long long l,long long r,long long d)
{
    if(l>t[v].r||r<t[v].l)
    return ;
    down(v);
    if(l<=t[v].l&&r>=t[v].r)
    {
        t[v].s+=d*(t[v].r-t[v].l+1);
        t[v].bj+=d;
        return ;
    }
    xg(v<<1,l,r,d);
    xg(v<<1|1,l,r,d);
    up(v);
}
void xg1(long long v,long long l,long long r,long long d)
{
    if(l>t[v].r||r<t[v].l)
    return ;
    down(v);
    if(l<=t[v].l&&r>=t[v].r)
    {
        t[v].s+=(ds[v]+1)*d*(t[v].r-t[v].l+1);
        t[v].bj1+=d;
        return ;
    }
    xg1(v<<1,l,r,d);
    xg1(v<<1|1,l,r,d);
    up(v);
}
long long cz(long long v,long long x)
{
    if(x>t[v].r||x<t[v].l)
    return 0;
    down(v);
    if(t[v].l==t[v].r)
    return t[v].s;
    return cz(v<<1,x)+cz(v<<1|1,x);
}
int main()
{
    long long i,j,x,y,z;
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;i++)
    scanf("%lld",&d[i]);
    for(i=1;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        ad(x,y);
        ad(y,x);
    }
    dfs(1,0);
    bd(1,1,n);
    for(i=1;i<=n;i++)//插入节点的初始权值
    xg(1,st[i],ed[i],d[i]);
    for(i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        if(x==1)
        {
            scanf("%lld",&z);
            xg(1,st[y],ed[y],z);
        }
        if(x==2)
        {
            scanf("%lld",&z);
            xg1(1,st[y],ed[y],z);//增加(deep[y]+1)*z的部分
            xg(1,st[y],ed[y],-z*de[y]);//减少deep[x]*z的部分
        }
        if(x==3)
        printf("%lld\n",cz(1,st[y]));
    }
    return 0;
}