[题解]洛谷P4114:Qtree1

原题链接:P4114 Qtree1


思路

树链剖分裸题,将边权移至儿子节点作为点权,树剖后线段树维护单点修改和区间最大值即可。

由于是首次撰写树剖题解,详细写一下树链剖分的学习笔记。

树链剖分

在这里指重链剖分。其实就是两遍dfs。

一些概念

  • 重儿子:子树大小最大的儿子
  • 重链:从某点出发,一直走重儿子直到叶子节点所经过的链
  • 轻边:不属于任何一条重链的边

示意图

图中红点标记为每个重链的最高点(注意,有的重链只有一个点),加粗的边构成的链是重链,其余边是轻边。

算法过程

前面已经说了是两遍dfs。

  • 任选根节点,第一遍dfs确定父亲同时维护深度dep、大小siz和重儿子son
  • 第二遍dfs记录dfs序dfn和每个节点所属重链的开始节点top,有时还需要维护离开时的标记end

也就是这样:

int dep[MAXN],fat[MAXN],siz[MAXN],son[MAXN],tim=0;
int dfn[MAXN],end[MAXN],top[MAXN];
void dfs1(int u,int f){
    u[dep]=f[dep]+1;
    u[fat]=f;
    u[siz]=1;
    u[son]=0;
    for(int i=u[head],v;i;i=i[nxt])
        if((v=to[i])!=f){
            dfs1(v,u);
            u[siz]+=v[siz];
            if(v[siz]>u[son][siz])u[son]=v;
        }
}
void dfs2(int u,int f){
    u[dfn]=++tim;
    u[top]=(u==f[son])?f[top]:u;
    if(u[son])dfs2(u[son],u);
    for(int i=u[head],v;i;i=i[nxt])
        if((v=i[to])!=f&&v!=u[son])dfs2(v,u);
    u[end]=tim;
}

随便初始化然后直接执行dfs1(1,0);dfs2(1,0);,完成后就可以利用dfn数组在线段树上乱搞啦~

附注与代码

注意,由于本题是把边权移至子节点来做,所以线段树区间查询时不应包含LCA,直接两侧取max即可。

R22548923 R22548980

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100003;
int n;
//白调了,无向图两倍大小,请 
int head[MAXN<<1],nxt[MAXN<<1],to[MAXN<<1],cnt=0,tim=0;
int ui[MAXN],vi[MAXN],vall[MAXN];
inline void add_edge(int u,int v){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    to[++cnt]=u;
    nxt[cnt]=head[v];
    head[v]=cnt;
}
int dep[MAXN],fat[MAXN],siz[MAXN],son[MAXN];
int dfn[MAXN],/*end[MAXN],*/top[MAXN];
void dfs1(int u,int f){
    u[dep]=f[dep]+1;
    u[fat]=f;
    u[siz]=1;
    u[son]=0;
    for(int i=u[head],v;i;i=i[nxt])
        if((v=to[i])!=f){
            dfs1(v,u);
            u[siz]+=v[siz];
            if(v[siz]>siz[son[u]])u[son]=v;
        }
}
void dfs2(int u,int f){
    u[dfn]=++tim;
    u[top]=(u==f[son])?f[top]:u;
    if(u[son])dfs2(u[son],u);
    for(int i=u[head],v;i;i=i[nxt])
        if((v=i[to])!=f&&v!=u[son])dfs2(v,u);
    //u[end]=cnt;
}
//int a[MAXN];
int mm[MAXN<<2];
inline void push_up(int rt){mm[rt]=max(mm[rt<<1],mm[rt<<1|1]);}
/*void build(int l,int r,int rt){
    if(l==r){mm[rt]=a[l];return;}
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    push_up(rt);
}*/
void update(int pos,int vl,int l,int r,int rt){
    if(pos<l||pos>r)return;
    if(pos==l&&pos==r){mm[rt]=vl;return;}
    int mid=(l+r)>>1;
    if(pos<=mid)update(pos,vl,l,mid,rt<<1);
    else update(pos,vl,mid+1,r,rt<<1|1);
    push_up(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L>R||r<L||l>R)return 0;
    if(L<=l&&r<=R)return mm[rt];
    int mid=(l+r)>>1;
    int ans=0;
    if(L<=mid)ans=max(ans,query(L,R,l,mid,rt<<1));
    if(mid<R)ans=max(ans,query(L,R,mid+1,r,rt<<1|1));
    return ans;
}
int get_ans(int x,int y){
    int rs=0;
    for(int ta=top[x],tb=top[y];ta!=tb;)
        if(dep[ta]>dep[tb])
            rs=max(rs,query(dfn[ta],dfn[x],1,n,1)),ta=top[x=fat[ta]];
        else
            rs=max(rs,query(dfn[tb],dfn[y],1,n,1)),tb=top[y=fat[tb]];
    if(dep[x]>dep[y])swap(x,y);
    return max(rs,query(dfn[x]+1,dfn[y],1,n,1));
}
int val[MAXN];
int main(){
    memset(head,0,sizeof(head));
    memset(dep,0,sizeof(dep));
    memset(siz,0,sizeof(siz));
    memset(son,0,sizeof(son));
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",ui+i,vi+i,vall+i);
        add_edge(i[ui],i[vi]);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<n;i++){//边权改点权 
        if(dep[ui[i]]>dep[vi[i]])swap(ui[i],vi[i]);
        val[vi[i]]=vall[i];
    }
    /*memset(a,0,sizeof(a));
    for(int i=1;i<n;i++)
        if(i[ui][dep]<i[vi][dep])a[i[vi][dfn]]=i[val];
        else a[i[ui][dfn]]=i[val];*/
    memset(mm,0,sizeof(mm));
    //build(1,n,1);
    for(int i=1;i<=n;i++)update(dfn[i],val[i],1,n,1);
    static char s[10];
    while(scanf("%s",s),s[0]!='D'){
        int x,y;
        scanf("%d%d",&x,&y);
        if(s[0]=='Q'){
            printf("%d\n",get_ans(x,y));
        }else{
            update(dfn[vi[x]],y,1,n,1);
        }
    }
    return 0;
}
最后修改:2019 年 08 月 11 日 10 : 20 AM
欢迎投食喵 ~

发表评论