【考试】【树链剖分】一道好题让你深入了解树链剖分

发布于 2018-08-31  959 次阅读


题目大意:

给你一棵树,每个点有点权,让你支持③种操作

(1)点x值加y

(2)以点x为根的子树加y

(3)定义(u,v)为u和v的点权和。求∑(u,v) (u<v&&lca(u,c)=x)

很好,前两个操作很简单,随便用线段树维护个dfs序就行,(什么?你不会?你可以先去入门 学习一下)

思考操作③,如果我们有一棵长相如此的树。我对点1询问操作(3)。

那么答案大概是(不用在意我的顺序):(2,3)(2,6)(2,7)(4,3)(4,6)(4,7)(5,3)(5,6)(5,7)+(1,2~7);

发现只有满足两个点不同时在1的某棵子树中才有贡献,和1与它所有儿子才有贡献。

那答案可以写成:

val[x]*(siz[x]-1)+query(x)-val[x]+(query(1)*(siz[x]-1-siz[1]))+.......+(query(n)*(siz[x]-1-siz[n]))

=val[x]*(siz[x]-1)+siz[x]*(query(1)+...+query(n))-query(1)*siz[1]-...-query(n)*siz[n]

=query(x)*siz[x]-val[x]-$\sum_{i=1}^{n}(query(i)*siz[i])$;(i为x的直接儿子)
(可以自己手推一下)

然后我们可以对于询问的每个点,按照上述式子写出一个n²log(n)的优秀算法(被菊花图卡)
哦,你或许能特判菊花得到一个优秀的sqrt(n³)log(n)的算法(显然还是会tle)
或者可以每次维护x的答案同时向上向下传修改,(可以过菊花但会被链卡)
貌似这题向不可做方向发展了

考虑树链剖分的性质,轻链不会超log的长度,我们或许可以暴力的搞一搞。
对于询问$\sum_{i=1}^{n}query(i)\times siz[i]$我们可以看做分别对轻重链维护。
1. 对于重链
我们可以直接暴力用query(i)*siz[i].
2. 对于轻链
我们可以把他的贡献在每次更改时就更新,累加到他的fa[top]上,
然后直接计算,详细处理方法见代码(附件亲民注释)

#include <cstdio> 
#include <algorithm>

#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
const int N=400005;

inline int read() { char k=0;char sb;sb=getchar(); for(;sb<'0'||sb>'9';k=sb,sb=getchar()); int x=0;for(;sb>='0'&&sb<='9';sb=getchar())x=x*10+sb-'0'; if(k=='-')x=0-x;return x; }
struct data{int v,nxt;}edge[N];
int cnt,alist[N];
inline void add1(int u,int v){edge[++cnt]=(data){v,alist[u]},alist[u]=cnt;}
int n,m;
long long val[N],sum_val[N],sum_light[N],xs[N];
int fa[N];



/**shupao**/
int siz[N],dep[N],top[N],dfn[N],son[N],tot,num[N];
inline void dfs1(int x)
{
    siz[x]=1;dep[x]=dep[fa[x]]+1;sum_val[x]=val[x];
    //siz[x] 以x为根子树大小,dep[x]x的深度, sum_val以x为根的子树权值和 
    for(int i=alist[x];i;i=edge[i].nxt)
    {
        int v=edge[i].v;
        dfs1(v);siz[x]+=siz[v];sum_val[x]+=sum_val[v];
        if(siz[v]>siz[son[x]]) son[x]=v;//重儿子 
    }
}
inline void dfs2(int x)
{
    dfn[x]=++tot;num[tot]=x;//dfs序,线段树维护值 
    if(!top[x]) top[x]=x;//链顶节点, 
    if(son[x]) top[son[x]]=top[x],dfs2(son[x]);
    for(int i=alist[x];i;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==son[x]||v==fa[x]) continue;
        dfs2(v);
    }
}

/***下面是维护树剖的线段树**/
long long sum[N<<2],add[N<<2];
inline void pushdown(int p,int l,int r)
{
    if(!add[p]) return;
    int mid=(l+r)>>1;
    add[ls]+=add[p];add[rs]+=add[p];
    sum[ls]+=add[p]*(mid-l+1);sum[rs]+=add[p]*(r-mid);
    add[p]=0;
    return ;
}
inline void build(int p,int l,int r)
{
    if(l==r) {sum[p]=val[num[l]];return;}
    int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    sum[p]=sum[ls]+sum[rs];
}
inline void setadd(int p,int l,int r,int dl,int dr,int plus)
{
    if(dl<=l&&dr>=r){add[p]+=plus;sum[p]+=plus*(r-l+1);return ;}
    pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(dl<=mid) setadd(ls,l,mid,dl,dr,plus);
    if(dr>mid) setadd(rs,mid+1,r,dl,dr,plus);
    sum[p]=(sum[ls]+sum[rs]);
}
inline long long query(int p,int l,int r,int dl,int dr)
{
    if(dl<=l&&dr>=r){return sum[p];}
    pushdown(p,l,r);
    int mid=(l+r)>>1;
    long long res=0;
    if(dl<=mid) res+=query(ls,l,mid,dl,dr);
    if(dr>mid) res+=query(rs,mid+1,r,dl,dr);
//  printf("return=%d\n",res);
    return res;
}
inline void change(int x,long long tm)
{
    x=top[x];
    while(x!=1)//首先我要维护的是轻链
    {
        sum_light[fa[x]]+=tm*siz[x];//对于修改的贡献就是修改的大小*轻链的top的siz
       /// printf("x=%d fa[x]=%d sum=%d ojbk\n",x,fa[x],sum_light[fa[x]]);
        x=top[fa[x]];
    }
}
inline void re()//暴力维护一发轻链,预处理
{
    for(int i=1;i<=n;++i)
    for(int j=alist[i];j;j=edge[j].nxt)
    {
        int v=edge[j].v;
        if(v!=son[i])//v不是重儿子 
        {
            sum_light[i]+=sum_val[v]*siz[v];//把轻链的贡献放到他的重父亲上
            //只有询问他的父亲时才会有贡献(不懂?仔细想想,画图)
            xs[i]+=(long long)siz[v]*siz[v];
            //预理一发,后面要用
        }
    }
}
long long ta[N];
inline void tadd(int x,long long y)
{
    for(;x<=n;x+=x&-x) ta[x]+=y;
}
inline long long tq(int x)
{
    long long res=0;
    for(;x;x-=x&-x) res+=ta[x];
    return res;
}
signed main()
{
    //scanf("%d%d",&n,&m);
    n=read();m=read();
    for(int i=1;i<=n;++i) val[i]=read();
    for(int i=2;i<=n;++i){fa[i]=read();add1(fa[i],i);}
    dfs1(1);dfs2(1);build(1,1,n);re();
    /***ok****/
    for(int i=1;i<=m;++i)
    {
        int x,y;long long z;
        x=read();
        if(x==1)
        {
          y=read();z=read();
            change(y,z);setadd(1,1,n,dfn[y],dfn[y],z);
        }
        else if(x==2)
        {
          //  scanf("%d%lld",&y,&z);
          y=read();z=read();
            change(y,(long long)z*siz[y]);
            setadd(1,1,n,dfn[y],dfn[y]+siz[y]-1,z);
            tadd(dfn[y],z);tadd(dfn[y]+siz[y],-z);//用树状数组统计**某个点所代表子树**被加了多少
        }
        else
        {
            //scanf("%d",&y);
            y=read();
        //  printf("sb=%d\n",query(1,1,n,dfn[y],dfn[y]+siz[y]-1));
            long long ans=query(1,1,n,dfn[y],dfn[y]+siz[y]-1)*siz[y];
            ans-=query(1,1,n,dfn[y],dfn[y]);printf("res=%d\n",ans);
            //公式上的第一步↑
            //公式上的第二步↓
            if(son[y])//如果是重点,单独先减一发
                ans-=query(1,1,n,dfn[son[y]],dfn[son[y]]+siz[son[y]]-1)*siz[son[y]];
            ans=ans-sum_light[y]-tq(dfn[y])*xs[y];
            //-sum_light是维护的重点的轻儿子的贡献
            //-tq(dfn[y])*xs[y]刚才的xs预处理是siz*siz;
            //siz*tq=query  query*siz=我们要求的。
            //tq(x)指以x为根子树被加了多少  xs是以x为top的轻链大小的平方
            //这就是暴力维护轻链,sum_light[x]只有x是重点且x的轻链中被修改才会改,tq是x被修改才改
            //没懂可以私信
            printf("%lld\n",ans);
        }
    }
}

 

0.00 avg. rating (0% score) - 0 votes

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。