树

树链剖分

码力不足

Posted by JU on July 24, 2018

bzoj1036

#include <bits/stdc++.h>
#define sc(p) scanf("%d",&p)
#define sc2(p1,p2) sc(p1),sc(p2)
#define pr(p) printf("%d\n",p)
const int oo=2147483640;
const int N=1010000;
using namespace std;
struct EDGE { int v,nx; }lb[N<<1]; int topp[N],tot=1;
void add (int u,int v) { lb[++tot].v=v,lb[tot].nx=topp[u],topp[u]=tot; }
struct POINT { int siz,w,id,fa,h,top; }p[N];
void dfs1 (int u)
{
    p[u].siz=1,p[u].w=0;
    for (int kb=topp[u]; kb!=-1; kb=lb[kb].nx)
    {
        int v=lb[kb].v;
        if (v==p[u].fa) continue;
        p[v].fa=u,p[v].h=p[u].h+1;
        dfs1 (v);
        p[u].siz+=p[v].siz;
        if (p[v].siz>p[p[u].w].siz) p[u].w=v;
    }
}
int dfn=0;
void dfs2 (int u)
{
    p[u].id=++dfn;
    if (p[u].w) p[p[u].w].top=p[u].top,dfs2 (p[u].w);
    for (int kb=topp[u]; kb!=-1; kb=lb[kb].nx)
    {
        int v=lb[kb].v;
        if (v==p[u].w||v==p[u].fa) continue;
        p[v].top=v; dfs2 (v);
    }
}
int val[N],a[N];
struct TREE { int l,r,sum,ma; }t[N>>2];
void build (int p,int l,int r)
{
    t[p].l=l,t[p].r=r;
    if (l==r) { t[p].sum=t[p].ma=a[l]; return ; }
    int mid=(l+r)>>1,ls=p<<1,rs=ls|1;
    build (ls,l,mid),build (rs,mid+1,r);
    t[p].sum=t[ls].sum+t[rs].sum;
    t[p].ma=max (t[ls].ma,t[rs].ma);
}
void change (int p,int w,int d)
{
    if (t[p].l==w&&t[p].r==w) { t[p].sum=t[p].ma=d; return ; }
    if (t[p].r<w||t[p].l>w) return ;
    int mid=(t[p].l+t[p].r)>>1,ls=p<<1,rs=ls|1;
    if (w<=mid) change (ls,w,d);
    if (w> mid) change (rs,w,d);
    t[p].sum=t[ls].sum+t[rs].sum;
    t[p].ma=max (t[ls].ma,t[rs].ma);
}
int querysum (int p,int l,int r)
{
    if (t[p].l>=l&&t[p].r<=r) return t[p].sum;
    if (t[p].r< l||t[p].l> r) return 0;
    int mid=(t[p].l+t[p].r)>>1,ls=p<<1,rs=ls|1,ans=0;
    if (l<=mid) ans+=querysum (ls,l,r);
    if (r> mid) ans+=querysum (rs,l,r);
    return ans;
}
int queryma (int p,int l,int r)
{
    if (t[p].l>=l&&t[p].r<=r) return t[p].ma;
    if (t[p].r< l||t[p].l> r) return 0;
    int mid=(t[p].l+t[p].r)>>1,ls=p<<1,rs=ls|1,ans=-oo;
    if (l<=mid) ans=max (ans,queryma (ls,l,r));
    if (r> mid) ans=max (ans,queryma (rs,l,r));
    return ans;
}
int query (int kind,int x,int y)
{
    int ans= (kind==1) ? 0 : -oo;
    while (p[x].top!=p[y].top)
    {
        if (p[p[x].top].h<p[p[y].top].h) swap (x,y);
        ans= (kind==1) ? (ans+querysum (1,p[p[x].top].id,p[x].id)) : (max (ans,queryma (1,p[p[x].top].id,p[x].id)));
        x=p[p[x].top].fa;
    }
    if (p[x].h<p[y].h) swap (x,y);
    ans= (kind==1) ? (ans+querysum (1,p[y].id,p[x].id)) : (max (ans,queryma (1,p[y].id,p[x].id)));
    return ans;
}
int main()
{
    memset (topp,-1,sizeof (topp));
    int n; sc(n);
    for (int i=1; i<n; i++)
    {
        int x,y; sc2(x,y);
        add (x,y),add (y,x);
    }
    for (int i=1; i<=n; i++) sc(val[i]);
    p[1].h=1,dfs1(1);
    p[1].top=1,dfs2(1);
    for (int i=1; i<=n; i++) a[p[i].id]=val[i];
    build (1,1,n);
    int lgj; sc(lgj);
    while (lgj--)
    {
        char sb[10]; int x,y;
        scanf ("%s%d%d",sb,&x,&y);
        if (sb[0]=='C') change (1,p[x].id,y);
        if (sb[1]=='S') pr(query (1,x,y));
        if (sb[1]=='M') pr(query (2,x,y));
    }
    return 0;
}

树链剖分

概念

树链剖分就是将树分割成多条链，然后利用数据结构（线段树、树状数组等）来维护这些链。

树链

树链是树上的一条路径，这里特别规定：树链上每一个点深度不同。
即：每一条树链都是沿着深度从小到大延伸的。

轻重链划分

用一种方案把一棵树上所有的点划分到树链中，使得每一个点在且仅在一条树链上。
重儿子：每一个点的子节点中，子树大小最大的节点。
轻儿子：除了重儿子以外的子节点。
重链：每一个点和它的重儿子在同一条重链上。每个点在且仅在一条重链上。
轻链：每一个点连接它的轻儿子的边，长度为1，每个点可能连着若干条轻链。
这里划分出来的树链实际是重链，轻链用来维持树原来的形态。

用途

引理：任意点到根的路径最多经过$\log_{}{n}$条重链。
那么给每条重链建一棵线段树，任意点到根的操作就可以转化为$\log_{}{n}$条重链的操作，$O(\log_{}^{2}{n})$
实际保证重链上的点编号连续，可以只建一棵线段树，一条重链即为一个区间。

做法

对于每个点记以下内容：子树大小siz，重儿子w，编号id，重链的开头top，每个点的父亲fa，深度h。

dfs1

void dfs1 (int u)
{
    p[u].siz=1,p[u].w=0;
    for (int kb=topp[u]; kb!=-1; kb=lb[kb].nx)
    {
        int v=lb[kb].v;
        if (v==p[u].fa) continue;
        p[v].fa=u,p[v].h=p[u].h+1;
        dfs1 (v);
        p[u].siz+=p[v].siz;
        if (p[v].siz>p[p[u].w].siz) p[u].w=v;
    }
}

dfs2

void dfs2 (int u)
{
    p[u].id=++dfn;
    if (p[u].w) p[p[u].w].top=p[u].top,dfs2 (p[u].w);
    for (int kb=topp[u]; kb!=-1; kb=lb[kb].nx)
    {
        int v=lb[kb].v;
        if (v==p[u].w||v==p[u].fa) continue;
        p[v].top=v; dfs2 (v);
    }
}

操作

任意一个点x所在树链的开头是p[x].top，再往上p[p[x].top].fa就进入了另外一条树链。
在这种设计下，只能从下往上找，所以链上操作是从链的两端分别往上找，直到到达LCA为止。

具体过程

设链的两端为x和y。
首先，判断x和y是否在同一条重链上，即判断p[x].top和p[y].top是否相等。
不在同一条重链的情况：
比较p[p[x].top].h和p[p[y].top].h，选出比较大的，这里假设p[p[x].top].h比较大。
处理p[p[x].top].id到p[x].id的区间，即处理x到重链的开头。
x=p[p[x].top].fa，跳到上一条重链上，回到判断是否在同一条重链。
同一条重链的情况：
设p[x].h>p[y].h，那么我们需要处理的是p[x].id到p[y].id的区间。（这里y是LCA）
由于已经处理到LCA了，操作完毕。

栗

询问链上点权和与最大值。

int query (int kind,int x,int y)
{
    int ans= (kind==1) ? 0 : -oo;
    while (p[x].top!=p[y].top)
    {
        if (p[p[x].top].h<p[p[y].top].h) swap (x,y);
        ans= (kind==1) ? (ans+querysum (1,p[p[x].top].id,p[x].id)) : (max (ans,queryma (1,p[p[x].top].id,p[x].id)));
        x=p[p[x].top].fa;
    }
    if (p[x].h<p[y].h) swap (x,y);
    ans= (kind==1) ? (ans+querysum (1,p[y].id,p[x].id)) : (max (ans,queryma (1,p[y].id,p[x].id)));
    return ans;
}

其他

每一个点表示它到它的父亲之间的边权，不同重链上的处理不变。
在同一条重链上时，注意不要把LCA到它父亲的边算进来。

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：树链剖分”
CATALOG
    FRIENDS