真的是假的吗?

题解 P3979 【遥远的国度】
题解

好像除了换根操作之外就是板子

那我们就讲下换根吧
换根 : 我们分3种情况讨论

1 . 如果now 和 root 重合 ,那就是查询整棵树 ,直接输出tmin[1]就好了

2 . 如果LCA(now,root) != now 这时根与now没有关系,直接查询now的子树即可

3 . 如果LCA(now,root) = now

这时就比较麻烦了

我们可以先找一下now的所有儿子

由于 一个子树的dfs序是连续的
所以 如果这个儿子的id大于等于root

并且这个子树中的最大dfs序(id[son]+size[son]-1)小于等于当前的root

那么就可以判断出root在这个儿子中或者就是这个儿子,记录下这个儿子

还是那句话 :一个子树的dfs序是连续的

这时now的子树就是去除包含root的那个儿子的子树的整棵树了 

然而我讲的并不清楚,要是实在不懂可以手胡一下对吧

放一下代码,帮助各位dalao理解下吧

  #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
# define ls now<<1
# define rs now<<1|1
const int M = 100005 ;
const int inf = 2100000000 ;
using namespace std;
inline int read(){
    char c=getchar(); int x=0,w=1;
    while(c>'9'||c<'0'){if(c=='-') w=-1 ;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*w;
}
int n,m;
struct E{
    int nex,to;
}edge[M<<1];
int hea[M],num;
inline void add_edge(int from,int to){
    edge[++num].nex=hea[from];
    edge[num].to=to;
    hea[from]=num;
}
int fa[M],dep[M],size[M],son[M];
int val[M],root;
void dfs1(int u,int father,int deep){
    dep[u]=deep; 
    fa[u]=father;
    size[u]=1 ;
    int Maxson=-1;
    for(int i=hea[u];i;i=edge[i].nex){
        int v=edge[i].to;
        if(v==father) continue ;
        dfs1(v,u,deep+1);
        size[u]+=size[v];
        if(size[v]>Maxson){
            Maxson=size[v];
            son[u]=v;

        }
    }
}
int id[M],cnt,top[M],p[M];
void dfs2(int u,int topf){
    top[u]=topf; 
    id[u]=++cnt;
    p[cnt]=val[u];
    if(!son[u]) return ;
    dfs2(son[u],topf);
    for(int i=hea[u];i;i=edge[i].nex){
        int v=edge[i].to;
        if(!id[v])
          dfs2(v,v);
    }
}
inline int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<=dep[y]?x:y;
}
int tmin[M<<2],tag[M<<2];
inline void pushup(int now){
    tmin[now]=min(tmin[ls],tmin[rs]);
}
inline void pushdown(int now){
    if(tag[now]!=-1){
        tmin[ls]=tmin[rs]=tag[now];
        tag[ls]=tag[rs]=tag[now];
        tag[now]=-1;
    }
}
void Build(int l,int r,int now){
    tag[now]=-1;
    if(l==r){
        tmin[now]=p[l];
        return ;
    }
    int mid=(l+r)>>1;
    Build(l,mid,ls);
    Build(mid+1,r,rs);
    pushup(now);
}
void change(int L,int R,int C,int l,int r,int now){
    if(l==L&&r==R){
        tmin[now]=C;
        tag[now]=C;
        return ;
    }
    int mid=(l+r)>>1;
    pushdown(now);
    if(mid>=R) change(L,R,C,l,mid,ls);
    else if(mid<L) change(L,R,C,mid+1,r,rs);
    else{
        change(L,mid,C,l,mid,ls);
        change(mid+1,R,C,mid+1,r,rs);
    }
    pushup(now);
}
void change1(int x,int y,int C){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        change(id[top[x]],id[x],C,1,n,1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    change(id[x],id[y],C,1,n,1);
}
int query(int L,int R,int l,int r,int now){
    if(l>R||r<L) return inf;
    if(l>=L&&r<=R) return tmin[now];
    int mid=(l+r)>>1;
    pushdown(now);
    int Ans=query(L,R,l,mid,ls);
    Ans=min(Ans,query(L,R,mid+1,r,rs));
    return Ans;
}
int main(){
    n=read(); m=read();
    int u,v;
    for(int i=1;i<n;i++){
        u=read(); v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++) val[i]=read();
    root=read();
    dfs1(1,1,1);
    dfs2(1,1);
    Build(1,n,1);
    while(m--){
        int opt=read();
        if(opt==1){
            int x=read();
            root=x;
        }
        else if(opt==2){
            int u=read(),v=read(),w=read();
            change1(u,v,w);
        }
        else{
            int x=read();
            if(x==root) printf("%d\n",tmin[1]);
            else{
                int lca=LCA(x,root);
                if(lca==x){
                    int y;
                    for(int i=hea[x];i;i=edge[i].nex){
                        int v=edge[i].to;
                        if(id[v]<=id[root]&&id[v]+size[v]-1>=id[root]){
                            y=v;
                            break;
                        }
                    }
                    int Ans=query(1,id[y]-1,1,n,1);
                    Ans=min(Ans,query(id[y]+size[y],n,1,n,1));
                    printf("%d\n",Ans);
                }
                else printf("%d\n",query(id[x],id[x]+size[x]-1,1,n,1));
            }
        }
    }
    return 0;
}
评论