1. 前言

如果给你一棵树,求点u到点v路径上点的权值之和,你可能会说:倍增啊!

那如果出题人:我还要你支持修改某个点的权值!

或者再j一点:我还要你支持修改点u到点v路径上点的权值!

那就得用树链剖分了。

2. 什么是树链剖分

上面那个问题,树上区间修改。

区间修改最常见做法就是线段树了。

那我们怎么用线段树维护一颗。。。普通的树呢?

那就给普通的树的每个节点标个号,然后放线段树里呗。区间维护。

但如果随便标号,那点u到点v路径不一定标号是连续的啊,你线段树维护个j啊

所以我们现在引入一个(堆)姿势:



那么这些姿势有什么用呢?先看一道题吧!

传送门= ̄ω ̄=

我们先来看张图:

图中标在边上了,但也不影响我们学。。。

标号方法是:跑dfs,先给当前节点标号,再给重儿子标号(重儿子和当前节点在一个重链上),然后对重儿子递归,最后给剩下的别的儿子标号(别的儿子不和当前节点在一个重链上,所以新建重链,把新建的重链的顶端节点设为那个”别的儿子“)、递归(图中是先给重(zhong)边标号,再给剩下的边标号)。标号从小到大。

不难发现一条重链上的标号是连续的,比如点1到点14,点2到点12

这意味着在线段树中,它们是在一个连续的区间里的,而不是像随便标号时断断续续的。

这样就很好用线段树处理了。

如果两个节点不在一条重链上呢?比如图中的点11和点10,我们要求它们之间的路径上的点权和

那我们就看,点11所在的重链是11->6->2,点10所在的重链是10(10所在的重链只有一个点,就是10)。所以我们就先求出重链11->6->2上的点权和、重链10上的点权和。这两条重链在线段树上都是一段连续的区间,可以直接log2n求出

这时候我们发现还有4->1的重链没有计算,就把它的点权和计算出来,三个重链的点权和加在一起就得到了答案。

所以我们要记录的是:
1. pos[i] 点i的标号
2. top[i] 点i所在重链的顶端节点
3. siz[i] 以点i为根的子树的大小
4. dep[i] 点i的深度
5. fa[i] 点i的父亲节点

我们先跑一边dfs,算出fa、size、dep

然后再跑一边dfs,根据size[i]找出点i的重儿子,然后算出pos、top。

具体代码:

void init1(int u)//第一个dfs
{
    siz[u]=1,dep[u]=dep[fa[u]]+1;
    for(int i=0;i<g[u].size();i++)//g[u]为点u的邻接表
        if(g[u][i]!=fa[u])fa[g[u][i]]=u,init1(g[u][i]),siz[u]+=siz[g[u][i]];//向下递归
}
void init2(int u)//第二个dfs
{
    int nxt=0,maxn=0;pos[u]=cnt++;//设置pos[u]
    for(int i=0;i<g[u].size();i++)//找出重儿子
        if(g[u][i]!=fa[u]&&siz[g[u][i]]>maxn)nxt=g[u][i],maxn=siz[g[u][i]];
    if(!nxt)return;//不存在重儿子就return
    top[nxt]=top[u],init2(nxt);//把重儿子加到u所在的重链里,然后递归重儿子
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&g[u][i]!=nxt)
            top[g[u][i]]=g[u][i],init2(g[u][i]);//新建重链
}

搞完这些就很easy了,因为一段重链在线段树里是一段连续的区间(这是坠重要的)。

我们在查询/修改从点u到点v的路径时,先找到所在重链的顶端节点(top)深度较深的(因为这样能让u和v同步提升,防止一个提到根节点了,另一个还没提,这时候你就不知道提谁了),注意不能按照u和v的深度来提!比如top较深的点是u,然后就用线段树处理区间$[pos[top[u]],pos[u]]$(因为top[u]的标号一定比u要小),再设置u为fa[top[u]],把u往上提,直至u和v在一条重链上(即top[u]==top[v])。这时候可能u和v之间还有一段距离,此时u和v已经在一条重链上,直接处理它们之间的区间就行了。

然后复杂度就是:$O(Nlog_{2} N+Qlog^{2} N)$

同时这个复杂度也是一般的树链剖分的复杂度。因为重链个数不会超过$log_{2} N$个,线段树复杂度是$log_{2} N$的。网上有证明,我就不做过多赘述

代码:

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
#define NS (30005)
using namespace std;
struct N{int l,r,max,sum;N(){l=r=max=sum=0;}}e[NS<<2];
int n,fa[NS],dep[NS],siz[NS],pos[NS],top[NS],w[NS],cnt=1,q;
char opt[10];
vector<int> g[NS];
void update(int a)
{e[a].max=max(e[LS(a)].max,e[RS(a)].max),e[a].sum=e[LS(a)].sum+e[RS(a)].sum;}
void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r;
    if(l==r){e[a].sum=e[a].max=w[l];return;}
    build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a)),update(a);
}
void change(int x,int k,int a)
{
    if(e[a].l==x&&e[a].r==x){e[a].sum=e[a].max=k;return;}
    if(x<=((e[a].l+e[a].r)>>1))change(x,k,LS(a));
    else change(x,k,RS(a));
    update(a);
}
int query_sum(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].sum;
    int tot=0;
    if(l<=((e[a].l+e[a].r)>>1))tot+=query_sum(l,r,LS(a));
    if(r>((e[a].l+e[a].r)>>1))tot+=query_sum(l,r,RS(a));
    return tot;
}
int query_max(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].max;
    int tot=INT_MIN;
    if(l<=((e[a].l+e[a].r)>>1))tot=max(tot,query_max(l,r,LS(a)));
    if(r>((e[a].l+e[a].r)>>1))tot=max(tot,query_max(l,r,RS(a)));
    return tot;
}
void init1(int u)
{
    siz[u]=1,dep[u]=dep[fa[u]]+1;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u])fa[g[u][i]]=u,init1(g[u][i]),siz[u]+=siz[g[u][i]];
}
void init2(int u)
{
    int nxt=0,maxn=0;pos[u]=cnt++;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&siz[g[u][i]]>maxn)nxt=g[u][i],maxn=siz[g[u][i]];
    if(!nxt)return;
    top[nxt]=top[u],init2(nxt);
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&g[u][i]!=nxt)
            top[g[u][i]]=g[u][i],init2(g[u][i]);
}
int query(int a,int b,bool f)
{
    int tot=f?0:INT_MIN;
    while(top[a]!=top[b])
    {
        if(dep[top[a]]>dep[top[b]])swap(a,b);
        if(f)tot+=query_sum(pos[top[b]],pos[b],1);
        else tot=max(tot,query_max(pos[top[b]],pos[b],1));
        b=fa[top[b]];
    }
    if(pos[a]>pos[b])swap(a,b);
    if(f)tot+=query_sum(pos[a],pos[b],1);
    else tot=max(tot,query_max(pos[a],pos[b],1));
    return tot;
}
int main()
{
    scanf("%d",&n);
    for(int i=1,a,b;i<n;i++)
        scanf("%d%d",&a,&b),g[a].push_back(b),g[b].push_back(a);
    init1(1),top[1]=1,init2(1);
    for(int i=1;i<=n;i++)scanf("%d",&w[pos[i]]);
    build(0,cnt-1,1),scanf("%d",&q);
    for(int i=1,a,b;i<=q;i++)
    {
        scanf("%s%d%d",opt,&a,&b);
        if(!strcmp(opt,"CHANGE"))change(pos[a],b,1);
        else if(!strcmp(opt,"QMAX"))printf("%d\n",query(a,b,0));
        else printf("%d\n",query(a,b,1));
    }
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

3 条评论

TPLY · 2018年1月15日 7:40 下午

ztO (ABS)&&(XZY) Orz

    konnyakuxzy · 2018年1月15日 8:19 下午

    OrzLTP赶紧膜Orz
    这种树链剖分您早就学会了吧QvQ
    Orz太强了
    就不要J型D蒟蒻惹QvQ
    话说boshiDalao正在翻译英文题目Orz
    我都没资格翻译啊QvQ

      TPLY · 2018年1月15日 8:36 下午

      刚刚开始学树剖emm
      说了我很弱啦
      刚刚才A的树的统计(我弱死了)

        TPLY · 2018年1月15日 8:41 下午

        有没有常数小点的板子,我的书剖常数大得要死

          konnyakuxzy · 2018年1月15日 9:17 下午

          啊?
          我觉得我的板子挺好啊
          好像没被卡过诶QvQ
          害怕.jpg

          boshi · 2018年1月15日 9:19 下午

          树剖主要是线段树的常数要小。查询修改反之和倍增没啥两样,常数可以忽略(前提是你不做无用的查询)。所以你需要学常数小的线段树

boshi · 2017年6月30日 3:31 下午

你觉得找重儿子是不是在init1()里方便一些。就可以少几个循环。

void init1(int x,int fat,int d)
{
    dep[x]=d,fa[x]=fat,siz[x]=1;
    for(int i=fst[x];i!=-1;i=nxt[i])
        if(v[i]!=fat)
        {
                init1(v[i],x,d+1);
                siz[x]+=siz[v[i]];
                if(son[x]==-1||siz[v[i]]>siz[son[x]])son[x]=v[i];
        }
}
void init2(int x,int tp)                               //tp=重链父节点
{
    top[x]=tp,pos[x]=++tim,rak[tid[x]]=x;
    if(son[x]==-1)return;
    init2(son[x],tp);
    for(int i=fst[x];i!=-1;i=nxt[i])if(v[i]!=son[x]&&v[i]!=fa[x])init2(v[i],v[i]);
}

boshi · 2017年6月29日 10:00 下午

膜膜膜太强了

    konnyakuxzy · 2017年6月29日 10:06 下午

    哈哈哈你发的没我快= ̄ω ̄=
    <(= ̄ˇ ̄=)>

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *