sup-extra 树链剖分

Posted at 2019-08-05 ICPC 

树链剖分

前言

​ 该说不愧是数据结构问题吗……写起来代码量意外的大啊……并且枯燥程度也不低啊……不过说实话还是很锻炼人的。

使用范围与思路

​ 基本上树上问题的解决还是离不开dfs与bfs啊。如果说lca解决的是两点间的最近父节点的问题，那树链剖分解决的就是两点间路径上的问题。不过解决的基本上都是点权问题，（反正树的节点联到父节点的边只有一条，点权边权没区别的吧？转换一下就好），然后诸如区间最值啊，区间和啊等等各种线段树能解决的问题都能解决。或者不如说树链剖分就是把树上的问题，转换成了线段树能处理的区间数的问题。

​ 树链剖分需要掌握的前置知识就是dfs序。这里也提一下dfs序和欧拉序列的区别。两者非常相似，都是按照dfs的顺序来确定点的编号，但dfs序只在访问到点a的时候给点a一个序号，而欧拉序列则会在点b访问结束回退到点a的时候再度给点a一个值。这导致了dfs序中每个点只会出现一次，整体长度为n，而欧拉序列由于一进一出，最终长度为 2 * n -1。欧拉序列的应用可以见RMQ转LCA问题

​ 树链剖分的使用主要分为两部分，首先是将树分解成链，然后针对各种树上的询问要转换成链上的询问，抛给线段树或树状数组或别的什么来解决。

​ **将树分解成链的部分 **：使用两次dfs，第一次需要处理出针对每个父节点的重儿子，同时初始化节点的一些通用属性（比如深度、父亲）。第二次则是构成dfs序。构成dfs序的时候要针对点赋值对应编号，针对编号赋值相应的权值，赋值该点的链头，并且优先dfs重儿子，来保持重链的性质。其他的轻链链头就是自身了，dfs一下随便赋个值就好。另外要注意判断有没有重儿子再往下dfs。

​ 转换树上询问的部分：写这个地方的函数可以说是非常难受了。首先你要判断询问的a b两点的链头相同不相同，不相同的情况下就挑链头深度更深的链，解决链头到链上节点的询问，然后我们从链头跳到链头的父节点，来到了新的链上，重复刚才的判断。当新的a b 到了同一条链上时就能通过点深度来解决询问了。

​ 树链剖分题目做了几道，整体感觉难点一来是代码非常长，要考虑的问题非常多，比较容易有细节上的错误；二来就是比较考验你的线段树功力，线段树作为真正解决问题的部分，如果写的不太行那树链剖分多么正确也没用。

题目及代码

树的统计Count HYSBZ - 1036

单点修改+区间最值，真的版题

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=100005;
const int INF=0x3f3f3f3f;
struct Node{
    int fa,son;
    int deep,siz;
    int val;
    int top, pos;
}node[maxn];
vector<int> tree[maxn];//反正边的信息在转换成区间后就不需要了
//随便拿个vector存一下吧
int dfsarray[maxn],tot;
void dfs1(int u,int fa){//第一个DFS用来处理出重儿子，并且从vector中得到树的父亲与深度信息
    node[u].fa=fa;
    node[u].son=0;
    node[u].siz=1;
    node[u].deep=node[fa].deep+1;
    for(int i=0;i<tree[u].size();++i){
        int v=tree[u][i];
        if(v!=fa) {
            dfs1(v,u);
            node[u].siz+=node[v].siz;
            if(node[node[u].son].siz<node[v].siz){
                node[u].son=v;
            }
        }
    }
}
void dfs2(int u,int fa,int ancient){
    node[u].top=ancient;
    node[u].pos=++tot;
    dfsarray[tot]=node[u].val;
    if(node[u].son)
        dfs2(node[u].son,u,ancient);
    for(int i=0;i<tree[u].size();++i){
        int v=tree[u][i];
        if(v!=fa&&v!=node[u].son){
            dfs2(v,u,v);
        }
    }
}
struct line{
    int l,r,sum,max;
}ltree[maxn<<2];//真的刺激，晚上再写吧
//结果不仅晚上没写第二天也没写
void build(int l,int r,int k){
    ltree[k].l=l,ltree[k].r=r;
    if(l==r){
        ltree[k].sum=dfsarray[l];
        ltree[k].max=dfsarray[l];
        return ;
    }
    else{
        int mid=(l+r)>>1;
        build(l,mid,k<<1);
        build(mid+1,r,k<<1|1);
        ltree[k].sum=ltree[k<<1].sum+ltree[k<<1|1].sum;
        ltree[k].max=max(ltree[k<<1].max,ltree[k<<1|1].max);
    }
}
void change(int k,int val,int loca){
    if(ltree[k].l==ltree[k].r) {
        ltree[k].sum=val;
        ltree[k].max=val;
        return;
    }
    int mid=(ltree[k].l+ltree[k].r)>>1;
    if(loca<=mid) change(k<<1,val,loca);
    else change(k<<1|1,val,loca);
    ltree[k].sum=ltree[k<<1].sum+ltree[k<<1|1].sum;
    ltree[k].max=max(ltree[k<<1].max,ltree[k<<1|1].max);

}
int qsum(int k,int l,int r){
    if(ltree[k].l==l&&ltree[k].r==r) return ltree[k].sum;
    int mid=(ltree[k].l+ltree[k].r)>>1;
    if(r<=mid) return qsum(k<<1,l,r);
    else if(l>mid) return qsum(k<<1|1,l,r);
    else return qsum(k<<1,l,mid)+qsum(k<<1|1,mid+1,r);
}
int qmax(int k,int l,int r){
    if(ltree[k].l==l&&ltree[k].r==r) return ltree[k].max;
    int mid=(ltree[k].l+ltree[k].r)>>1;
    if(r<=mid) return qmax(k<<1,l,r);
    else if(l>mid) return qmax(k<<1|1,l,r);
    else return max(qmax(k<<1,l,mid),qmax(k<<1|1,mid+1,r));
}
int sum_skip(int a,int b){
    int res=0;
    while(node[a].top!=node[b].top){
        int aa=node[a].top,bb=node[b].top;
        if(node[aa].deep<node[bb].deep) swap(a,b);
        res+=qsum(1,node[aa].pos,node[a].pos);
        a=node[a].top;
    }
    if(node[a].deep<node[b].deep) swap(a,b);
    res+=qsum(1,node[b].pos,node[a].pos);
    return res;
}
int max_skip(int a,int b){
    int res=-INF;
    while(node[a].top!=node[b].top){
        int aa=node[a].top,bb=node[b].top;
        if(node[aa].deep<node[bb].deep) swap(a,b);
        res=max(qmax(1,node[aa].pos,node[a].pos),res);
        a=node[a].top;
    }
    if(node[a].deep<node[b].deep) swap(a,b);
    res=max(qmax(1,node[b].pos,node[a].pos),res);
    return res;
}
int n;
int main(void)
{
    while(~scanf("%d",&n)){
        int a,b;
        for(int i=1;i<n;++i){
            scanf("%d%d",&a,&b);
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        for(int i=1;i<=n;++i){
            scanf("%d",&node[i].val);
        }
        node[0].deep=0;
        dfs1(1,0);
        dfs2(1,0,1);
        build(1,n,1);
        int q;
        scanf("%d",&q);
        while(q--){
            char com[10];
            int a,b;
            int res;
            scanf("%s%d%d",com,&a,&b);
            if(com[1]=='H'){
                change(1,b,node[a].pos);
            }
            else if(com[1]=='M'){

                if(node[a].pos<node[b].pos)
                    res=qmax(1,node[a].pos,node[b].pos);
                else res=qmax(1,node[b].pos,node[a].pos);
                printf("%d\n",res);
            }
            else if(com[1]=='S'){
                if(node[a].pos<node[b].pos)
                    res=qsum(1,node[a].pos,node[b].pos);
                else res=qsum(1,node[b].pos,node[a].pos);
                printf("%d\n",res);
            }
        }
    }
    return 0;
}

Query on a tree again! SPOJ - QTREE3

也是单点修改，每次修改会反向颜色，但是难点是找到离1最近的黑点，维护的时候判断有点麻烦。

第一次写的时候尝试用树状数组，然后发现辣鸡树状数组还是不好使啊，个人还是更会用线段树。

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=100005;
vector<int> tree[maxn];
//树状数组克我
struct node{
    int deep,son,siz;
    int posi,fa,top;
}Node[maxn];
struct lnode{
    int l,r,min;
}ltree[maxn<<2];
int n,q;
int tot,refer[maxn];
void init(){
    for(int i=1;i<=n;++i){
        tree[i].clear();
    }
    memset(Node,0,sizeof(Node));
}
int check_min(int a,int b){
    if(a==-1){
        return b;
    }
    else if(b==-1){
        return a;
    }
    if(Node[a].deep<Node[b].deep)
        return a;
    else return b;
}
void pre_build(int k,int l,int r){
    ltree[k].l=l,ltree[k].r=r,ltree[k].min=-1;
    if(l==r){
        return;
    }
    int mid=(l+r)>>1;
    pre_build(k<<1,l,mid);
    pre_build(k<<1|1,mid+1,r);
}
void change_color(int k,int num){
    if(ltree[k].l==ltree[k].r) {
        if(ltree[k].min!=-1)
            ltree[k].min=-1;
        else ltree[k].min=refer[ltree[k].l];
        return;
    }
    int mid=(ltree[k].l+ltree[k].r)>>1;
    if(mid>=num) change_color(k<<1,num);
    else change_color(k<<1|1,num);
    ltree[k].min=check_min(ltree[k<<1].min,ltree[k<<1|1].min);
}
int query(int k,int l,int r){
    if(ltree[k].min==-1) return -1;
    if(ltree[k].l==l&&ltree[k].r==r) return ltree[k].min;
    int mid=(ltree[k].l+ltree[k].r)>>1;
    if(r<=mid) return query(k<<1,l,r);
    else if(l>mid) return query(k<<1|1,l,r);
    else return check_min(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
}
void dfs1(int u,int fa){
    Node[u].deep=Node[fa].deep+1;
    Node[u].fa=fa;
    Node[u].siz=1;
    Node[u].son=0;
    for(int i=0;i<tree[u].size();++i){
        int v=tree[u][i];
        if(v!=fa){
            dfs1(v,u);
            Node[u].siz+=Node[v].siz;
            if(Node[Node[u].son].siz<Node[v].siz){
                Node[u].son=v;
            }
        }
    }
}
void dfs2(int u,int ancient){
    refer[++tot]=u;
    Node[u].posi=tot;
    Node[u].top=ancient;
    if(Node[u].son)
        dfs2(Node[u].son,ancient);
    for(int i=0;i<tree[u].size();++i){
        int v=tree[u][i];
        if(v!=Node[u].fa&&v!=Node[u].son){
            dfs2(v,v);
        }
    }
}
int split(int l,int r){
    int topl=Node[l].top,topr=Node[r].top;
    int res=-1;
    while(topl!=topr){
        if(Node[topl].deep>Node[topr].deep){
            swap(l,r);
            swap(topl,topr);
        }
        int tmp=query(1,Node[topr].posi,Node[r].posi);
        res=check_min(res,tmp);
        r=Node[topr].fa;
        topr=Node[r].top;
    }
    int tmp=query(1,Node[l].posi,Node[r].posi);
    return check_min(res,tmp);
}
int main(void)
{
    while(~scanf("%d%d",&n,&q)){
        init();
        for(int i=1;i<n;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        dfs1(1,0);
        dfs2(1,1);
        pre_build(1,1,n);
        int a,b;
        while(q--){
            scanf("%d%d",&a,&b);
            if(a==0){
                change_color(1,Node[b].posi);
            }
            else{
                int res=split(1,b);
                printf("%d\n",res);
            }
        }
    }
    return 0;
}