题解 P3178 【[HAOI2015]树上操作】

benny · 2018-12-22 21:40:38 · 题解

来一波树剖+超(du)级(liu)树状数组的题解，代码短，下面详细介绍

什么是树剖？

众所周知，在一颗树中，每个非根节点都有唯一的父亲，却有可能有很多的儿子。所谓树剖，是让所有非叶子节点，都挑选一个最偏爱的儿子，并且dfs优先搜索它

因为具体怎么偏爱的不同，一颗树有很多种剖分方式，像这样

别忘了我们优先搜索最偏爱的儿子，每个点赋予属性dfn为时间戳

观察到，无论怎么剖分，有：

每个点被唯一地放在一根链中（一个点也算链）
所有链的总长度（长度定义为链的顶点个数）为n
同一根链上的dfn具有连续性！！！（这一点用于本题操作3）
定义一个点c的重量为它子树中节点的个数，那么它子孙的dfn，可以一一对应到一个区间，这个区间左端点是dfn[c],长度为“c的重量”。别忘了，区间也有连续性

是不是有点乱？我们梳理一下。对于树中的每个点c，我们依次赋予了一些神秘的属性：

它的父亲fa
它的深度de,可以令de[c]=de[fa[c]]+1
重量wei，等于它儿子的总重量，再加1
它最偏爱的儿子son，具体怎么定义待会再议
它的dfn，注意是依据son的
它所在的链的顶端（显然是它的一个祖先），记作g g[c]=son[fa[c]]==c?g[fa[c]]:c即如果它是父亲的宠儿，那么它的链顶等于它父亲的链顶，否则就是它自己

你肯定不耐烦了，这样剖分有什么用？

很有用。我们如果要修改或询问树中一条路径上的信息，实质上是修改或询问许许多多条链的信息，更有意思的是，这些链上的dfn是连续的，可转化为区间操作。除此之外，我们有重链剖分和长链剖分两大利器，是非常非常非常有用的，本题就需要重链剖分

什么是重链剖分

我们定义son[c]为c最重的一个儿子之一。会发现一个神奇的性质

虽然一颗树被重链剖分会产生很多条链，但是对于树中每一个点，它到根节点的路上，经历的链的条数是很少的、有限的、甚至的lg级别的

啊，去根节点的路上，那些链又少又长

最深的11到1也只有1条链。那么怎么证明链的条数一定是lg级别呢？假设有一个坏蛋，想让11到根节点的路变得很多，他要怎么做？他要通过增加节点来让11（和它的祖先）不在是宠儿，从而将链切断。比如他可以让11不是宠儿：

从而让路径条数增加到2

很可惜，这个坏蛋是不能得逞的，因为他需要加很多很多的节点，才能略有收益。

以上是重链剖分的性质，希望你能感性理解。附上代码：


void dfs1(LL c,LL from)//第一遍dfs，置好fa,de,wei,son 
{
    LL i,y;
    fa[c]=from;
    de[c]=de[from]+1;
    wei[c]=1;
    son[c]=0;wei[0]=0;
    for(i=hea[c];i;i=nex[i])
    {
        y=poi[i];
        if(y==from) continue;
        dfs1(y,c);
        wei[c]+=wei[y];
        if(wei[y]>wei[son[c]])
            son[c]=y;//最重的儿子 
    }
}
void dfs2(LL c,LL from)//第二遍dfs，置好dfn和g 
{
    LL i,y;
    //printf("%lld\n",c);
    dfn[c]=++dfn[0];
    g[c]=son[from]==c?g[from]:c;//g定义为链顶 
    if(son[c])dfs2(son[c],c);//优先访问重儿子（最偏爱的儿子） 
    for(i=hea[c];i;i=nex[i])
    {
        y=poi[i];
        if(y==from||y==son[c]) continue;
        dfs2(y,c);
    }
}

在重链剖分中最偏爱的儿子是“重儿子”，链是重链

重链剖分有什么用

我们对于每个点，我们有了6大属性，和一条公理。可以猥琐欲为了。

两点(u和v)最近公共祖先LCA(本题不需要):还记得g是一个点的链顶吗？不断令u=fa[g[u]],v=fa[g[v]],不断地跳最终它们会在LCA处相遇

如果我们要修改或询问u到v路径上的点的所有关键值，实际上是修改或询问很少(lg)的区间。

具体来说，维护一个序列a，其下标是dfn，存的是关键值。
操作（包括修改和询问）节点u的关键值，就是在操作a[dfn[u]]
操作一条重链(u->v,u是v的祖先)上的所有关键值，实际上在操作:a[dfn[u]], a[dfn[u]+1], a[dfn[u]+2]..a[dfn[v]]
操作一个点到根节点路径上的所有关键值，本质上是在操作lg条重链（上一步）
操作两点间路径上所有的关键值（本题不需要），如果能处理LCA，本质上也是lg条重链
操作c的子树，记wei为c的重量，本质上在操作 a[dfn[c]],a[dfn[c]+1],a[dfn[c]+2],...a[dfn[c]+wei-1]

聪明的你一定不会傻傻的一个一个操作，而是用线段树喽，但本题我还会讲树状数组解法。

什么是长链剖分

长链剖分不如重链剖分应用广泛，本题不需要

重新定义son[c]为最长（或者叫深）的那个儿子，称作重(chang)儿子。

很可惜，长链剖分没有重链剖分“链少”的性质，它有时候链会多到根号n

但是，有一个好消息，长链剖分有其特有的性质

设c的k级祖先为y，（即y是c的祖先且两点距离为k），记len[y]为y所在长链的长度，那么有：

len[y]>=k

在这张图中，此性质尤为明显，使重链剖分可叹而不可及!

长链剖分有什么用

结合倍增nlgn预处理，他可以O(1)求节点c的k级祖先

预处理lg[x],表示以2为底的对数下取整
预处理顶点的属性：fa,de,len,son,g,dfn,其中len表示节点所在长链的长度
预处理st表，st[c][k]是个二维数组，表示c的"2的k次方"级祖先的编号，显然k是lg级的，而且有递推式

st[c][k]=st[st[c][k-1]][k-1]

预处理两个

vector<int> getup[maxn],

vector<int> getdown[maxn].

它们是二维的动态空间，含义如下。

仅在c处于链顶时（其他情况getup[c],getdown[c]为空）

getup[c][i]表示c的i级祖先，保证i<=len[c]

getdown[c][i]表示在c链中的i级子孙,保证i<=len[c]

时空复杂度均为len的和，也就是n。
"过半跳",每次询问c的k级祖先，首先设y=st[c][lg[k]], r=c和y的距离。r可以用深度来减，也可以是2的lg[k]次方，那么

r>=k/2,即

r>=k-r

"跳链顶",

tot=r+de[y]-de[g[y]],记录跳了多少步

设z=g[y]跳到链顶
不用写在程序里的小证明

我断言，c的k级祖先一定在向量getup[z]或getdown[z]里，理由如下。

根据长链的性质,len[y]>=r

又r>=k-r

所以

len[z]=len[y]>=r>=r-k>=dis(z,c的k级祖先),

如下图，颜色越粗表示越长

此时c的k级祖先在 getup[z]中

当然还有c的k级祖先在getdown[z]的情况
直接跳，返回getup[z][k-tot]。或者返回getdown[z][tot-k]

什么是超级树状数组

超级树状数组有，

2种基本操作：区间累加、前缀求和

1种延伸操作：区间求和（用前缀和减）

的nlgn数据结构，本质上是维护2个树状数组。虽然应用不如线段树广泛，但是代码短、细节少。

什么是树状数组

树状数组本质上有2种基本操作:单点累加，前缀求和。1种延伸操作:区间求和（用前缀和减）。简单地发一下代码：

void ADD(LL *a,LL i,LL x)//单点加 
{
    if(i>n) return;
    a[i]+=x;
    ADD(a,i+lowbit(i),x);
}

LL ASK(LL *a,LL i)//前缀求和 
{
    if(i==0) return 0;
    return ASK(a,i-lowbit(i))+a[i];
}

假设各位大佬已经会树状数组了，我们继续讨论

开始推公式

代码

注意我用大小写区分层次

LL lowbit(LL x){return x&(-x);}
void ADD(LL *a,LL i,LL x)//单点加 
{
    if(i>n) return;
    a[i]+=x;
    ADD(a,i+lowbit(i),x);
}

LL ASK(LL *a,LL i)//前缀求和 
{
    if(i==0) return 0;
    return ASK(a,i-lowbit(i))+a[i];
}
void Add(LL l,LL r,LL x)//区间加 
{
    //printf("Add %lld %lld %lld\n",l,r,x);
    ADD(d,l,x);
    ADD(d,r+1,-x);
    ADD(fd,l,x*(l-1));
    ADD(fd,r+1,-x*r);
}

LL Ask_(LL r)//前缀求和 
{
    return r*ASK(d,r)-ASK(fd,r); 
}
LL Ask(LL l,LL r)//区间求和 
{
    //printf("Ask %lld %lld\n",l,r);
    return Ask_(r)-Ask_(l-1);
}

总代码

个人觉得码风不错

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL maxn=200001;
const LL maxm=2*maxn;

LL hea[maxn],nex[maxm],poi[maxm];
LL w[maxn];
LL fa[maxn],de[maxn],wei[maxn],son[maxn];
LL g[maxn],dfn[maxn];
LL d[maxn],fd[maxn];
LL n,Q,i,j,k,t,x,y,type,u;

LL max(LL x,LL y){return x>y?x:y;}
LL lowbit(LL x){return x&(-x);}
void ADD(LL *a,LL i,LL x)//单点加 
{
    if(i>n) return;
    a[i]+=x;
    ADD(a,i+lowbit(i),x);
}

LL ASK(LL *a,LL i)//前缀求和 
{
    if(i==0) return 0;
    return ASK(a,i-lowbit(i))+a[i];
}
void Add(LL l,LL r,LL x)//区间加 
{
    //printf("Add %lld %lld %lld\n",l,r,x);
    ADD(d,l,x);
    ADD(d,r+1,-x);
    ADD(fd,l,x*(l-1));
    ADD(fd,r+1,-x*r);
}

LL Ask_(LL r)//前缀求和 
{
    return r*ASK(d,r)-ASK(fd,r); 
}
LL Ask(LL l,LL r)//区间求和 
{
    //printf("Ask %lld %lld\n",l,r);
    return Ask_(r)-Ask_(l-1);
}
LL ask(LL u)
{
    //printf("ask %lld\n",u);
    if(g[u]==g[1]) return Ask(dfn[1],dfn[u]);else
    return
        Ask(dfn[g[u]],dfn[u])+ask(fa[g[u]]);
}
void PW(LL i,LL j)
{
    k++;
    poi[k]=j;nex[k]=hea[i];hea[i]=k;
}

void PW2(LL i,LL j)
{
    PW(i,j);PW(j,i);
}

void dfs1(LL c,LL from)//第一遍dfs，置好fa,de,wei,son 
{
    LL i,y;
    fa[c]=from;
    de[c]=de[from]+1;
    wei[c]=1;
    son[c]=0;wei[0]=0;
    for(i=hea[c];i;i=nex[i])
    {
        y=poi[i];
        if(y==from) continue;
        dfs1(y,c);
        wei[c]+=wei[y];
        if(wei[y]>wei[son[c]])
            son[c]=y;//最重的儿子 
    }
}
void dfs2(LL c,LL from)//第二遍dfs，置好dfn和g 
{
    LL i,y;
    //printf("%lld\n",c);
    dfn[c]=++dfn[0];
    g[c]=son[from]==c?g[from]:c;//g定义为链顶 
    if(son[c])dfs2(son[c],c);//优先访问重儿子（最偏爱的儿子） 
    for(i=hea[c];i;i=nex[i])
    {
        y=poi[i];
        if(y==from||y==son[c]) continue;
        dfs2(y,c);
    }
}

int main()
{
    scanf("%lld%lld",&n,&Q);
    for(i=1;i<=n;i++) scanf("%lld",&w[i]);
    for(i=1;i<n;i++)
    {
        scanf("%lld%lld",&j,&t);
        PW2(j,t);
    }
    dfs1(1,0);
    dfs2(1,0);
    //for(i=1;i<=n;i++)
    //  printf("i=%lld dfn=%lld fa=%lld son=%lld g=%lld\n",i,dfn[i],fa[i],son[i],g[i]);
    for(i=1;i<=n;i++)
        Add(dfn[i],dfn[i],w[i]);
    while(Q--)
    {
        scanf("%lld%lld",&type,&u);
        if(type==1)
        {
            scanf("%lld",&x);
            Add(dfn[u],dfn[u],x);
        }else
        if(type==2)
        {
            scanf("%lld",&x);
            Add(dfn[u],dfn[u]+wei[u]-1,x);
        }else
        {
            printf("%lld\n",ask(u));
        }
    }
}