【Codeforces 342E】Xenia and Tree

Author Avatar
mrsrz 11月 18, 2019

树链剖分维护轻儿子信息

题目大意：

给定一棵树，初始标记 $1$ 为关键点，有两个操作：

  1. 新标记一个关键点。
  2. 给定点 $u$，问离 $u$ 最近的关键点到 $u$ 的距离。

题解：

有动态点分治和操作分块的做法了，这里再来一个不一样的。

考虑两点的距离的计算方法为 $\mathrm{dist}(u,v)=dep[u]+dep[v]-2\times dep[\mathrm{LCA}(u,v)]$。

考虑新加入一个关键点，在其所有祖先处记录信息，询问的时候，也直接在每个点的祖先上询问。相当于枚举最近公共祖先，计算其最小贡献。

但是更新答案时，会涉及到 $O(n)$ 个点的修改，而且每个点作为 LCA 的 $dep$ 要计算进去以便于取最小值。所以加入关键点时，更新的答案是一个类似等差数列。

这里也许可以使用树剖+李超树实现 $O(m\log^3 n)$，但可能因为一些重复计算之类的问题而出错而且复杂度看起来不好看虽然常数挺小。

考虑树链剖分维护轻儿子信息，每个点维护轻儿子所在子树和自己结点本身，结点深度最小和第二小的结点的深度及所在子树。然后，令最小的深度为 $d$，将 $d-2\times dep[v]$ 插入 $v$ 对应的线段树结点中，用以查询最小值。

更新的时候，显然只会在每条重链链顶更新，复杂度是 $O(\log^2 n)$。

查询的时候，对于重链上的，直接区间查询最小值即可。

但是当切换链的时候会出现一些情况：

  1. 链顶的父亲结点保存的最大值在链顶所在子树中。这里为了防止重复（其实不会错误因为计算的是最小值，出现此种情况最小值在之前应该已经更新了），使用次大值进行计算。
  2. 链顶的父亲结点的重儿子所在子树未计算贡献。那么我们再开一棵线段树，用来查询子树中深度最小的结点的深度，然后直接查询重儿子中的最小深度，计算贡献即可。

这里的复杂度也是 $O(\log^2 n)$ 的。

那么总时间复杂度 $O(m\log^2 n)$。

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+6;
struct edge{
    int to,nxt;
}e[N<<1];
struct info{
    int mx1,mx2,id1,id2;
}f[N];
int n,m,head[N],cnt,sz[N],son[N],dep[N],fa[N],top[N],dfn[N],idfn[N],idx;
int d[N<<2],dd[N<<2];
void build(int l,int r,int o){
    if(l==r)d[o]=(l==1)?-1:0x3f3f3f3f,dd[o]=d[o]==-1?1:d[o];else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        d[o]=min(d[o<<1],d[o<<1|1]);
        dd[o]=min(dd[o<<1],dd[o<<1|1]);
    }
}
void modify1(int l,int r,int o,const int&pos,const int&val){
    if(l==r)d[o]=val;else{
        const int mid=l+r>>1;
        if(pos<=mid)modify1(l,mid,o<<1,pos,val);else modify1(mid+1,r,o<<1|1,pos,val);
        d[o]=min(d[o<<1],d[o<<1|1]);
    }
}
void modify2(int l,int r,int o,const int&pos,const int&val){
    if(l==r)dd[o]=val;else{
        const int mid=l+r>>1;
        if(pos<=mid)modify2(l,mid,o<<1,pos,val);else modify2(mid+1,r,o<<1|1,pos,val);
        dd[o]=min(dd[o<<1],dd[o<<1|1]);
    }
}
int query1(int l,int r,int o,const int&L,const int&R){
    if(L<=l&&r<=R)return d[o];
    const int mid=l+r>>1;
    int ret=0x3f3f3f3f;
    if(L<=mid)ret=query1(l,mid,o<<1,L,R);
    if(mid<R)ret=min(ret,query1(mid+1,r,o<<1|1,L,R));
    return ret;
}
int query2(int l,int r,int o,const int&L,const int&R){
    if(L<=l&&r<=R)return dd[o];
    const int mid=l+r>>1;
    int ret=0x3f3f3f3f;
    if(L<=mid)ret=query2(l,mid,o<<1,L,R);
    if(mid<R)ret=min(ret,query2(mid+1,r,o<<1|1,L,R));
    return ret;
}
inline void update(int id,int sn,int depu){
    info&x=f[id];
    if(depu<x.mx1){
        x.mx2=x.mx1,x.id2=x.id1;
        x.mx1=depu,x.id1=sn;
        modify1(1,n,1,dfn[id],depu-2*dep[id]);
    }else
        if(depu<x.mx2){
            x.mx2=depu,x.id2=sn;
        }
}
void dfs(int now){
    sz[now]=1;
    for(int i=head[now];i;i=e[i].nxt)
    if(!dep[e[i].to]){
        dep[e[i].to]=dep[now]+1,fa[e[i].to]=now;
        dfs(e[i].to);
        sz[now]+=sz[e[i].to];
        if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
    }
}
void dfs2(int now){
    idfn[dfn[now]=++idx]=now;
    if(son[now])top[son[now]]=top[now],dfs2(son[now]);
    for(int i=head[now];i;i=e[i].nxt)
        if(e[i].to!=son[now]&&e[i].to!=fa[now])dfs2(top[e[i].to]=e[i].to);
}
void modify(int u){
    const int du=dep[u];
    modify2(1,n,1,dfn[u],du);
    update(u,u,du);
    while(top[u]!=1){
        update(fa[top[u]],top[u],du);
        u=fa[top[u]];
    }
}
int query(int u){
    int ret=0x3f3f3f3f,depu=dep[u];
    ret=min(ret,query2(1,n,1,dfn[u],dfn[u]+sz[u]-1)-depu);
    for(;;){
        int x=top[u],y=fa[top[u]];
        ret=min(ret,query1(1,n,1,dfn[x],dfn[u])+depu);
        if(y){
            ret=min(ret,(f[y].id1==x?f[y].mx2:f[y].mx1)+depu-2*dep[y]);
            if(son[y])
                ret=min(ret,query2(1,n,1,dfn[son[y]],dfn[son[y]]+sz[son[y]]-1)+depu-2*dep[y]);
            u=y;
        }else break;
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        e[++cnt]=(edge){v,head[u]},head[u]=cnt;
        e[++cnt]=(edge){u,head[v]},head[v]=cnt;
    }
    dfs(dep[1]=1),dfs2(top[1]=1);
    build(1,n,1);
    memset(f,0x3f,sizeof f);
    modify(1);
    while(m--){
        int op,u;
        cin>>op>>u;
        if(op==1)modify(u);else cout<<query(u)<<'\n';
    }
    return 0;
}
Powered by Hexo
Theme - Material