Luogu

分析

这种带换根的树上操作题就是 LCT板子 分类讨论...

首先那个链修改是不受换根影响的,我们只需要讨论子树查询。

设以 $1$ 为根时 $u$ 子树的点的 dfs 序在 $[st_u,ed_u]$ 内。假设查询的是 $u$ 子树,根是 $rt$,那么大概有以下几种情况:

  • $u=rt$,直接查所有点的最小值即可。
  • $\operatorname{lca}(u,rt)\neq u$,此时 $u$ 的子树就是以 $1$ 为根时 $u$ 的子树,直接查询 $[st_u,ed_u]$ 即可。
  • $\operatorname{lca}(u,rt)=u$,此时我们找到一个以 $1$ 为根是 $u$ 的子节点 $v$,满足 $rt$ 在子树 $v$ 内,那么此时 $u$ 的子树就是所有点去掉以 $1$ 为根时 $v$ 的子树。于是查询 $[1,st_v-1]\bigcup[ed_v+1,n]$ 即可。

写起来也比较休闲,只要码一堆板子上去就好了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,Q,rt; int w[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dep[N],fa[N],sz[N],hson[N],top[N];
int st[N],ed[N],pos[N],tim=0;
inline void dfs1(int u,int f) {
    dep[u]=dep[fa[u]=f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u); sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    top[u]=anc; st[u]=++tim,pos[tim]=u;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
    ed[u]=tim;
}
inline int getlca(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}

#define ls (o<<1)
#define rs (o<<1|1)
int minv[N<<2],assv[N<<2];
inline void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); }
inline void pushdown(int o) {
    if (assv[o]) {
        assv[ls]=minv[ls]=assv[o];
        assv[rs]=minv[rs]=assv[o];
        assv[o]=0;
    }
}
inline void build(int o,int l,int r) {
    if (l==r) { minv[o]=w[pos[l]]; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { assv[o]=minv[o]=w; return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
    if (ql>qr) return 2147483647;
    if (ql<=l&&r<=qr) return minv[o];
    int mid=(l+r)>>1,res=2147483647; pushdown(o);
    if (ql<=mid) res=min(res,query(ls,l,mid,ql,qr));
    if (qr>mid) res=min(res,query(rs,mid+1,r,ql,qr));
    pushup(o); return res;
}
#undef ls
#undef rs

int main() {
    n=read(),Q=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    for (re int i=1;i<=n;++i) w[i]=read();
    rt=read(),dfs1(1,0),dfs2(1,1); build(1,1,n);
    while (Q--) {
        int op=read();
        if (op==1) rt=read();
        else if (op==2) {
            int u=read(),v=read(),w=read();
            while (top[u]!=top[v]) {
                if (dep[top[u]]<dep[top[v]]) swap(u,v);
                modify(1,1,n,st[top[u]],st[u],w);
                u=fa[top[u]];
            }
            if (dep[u]<dep[v]) swap(u,v);
            modify(1,1,n,st[v],st[u],w);
        } else {
            int u=read();
            if (u==rt) printf("%d\n",query(1,1,n,1,n));
            else {
                int lca=getlca(u,rt);
                if (lca!=u) printf("%d\n",query(1,1,n,st[u],ed[u]));
                else {
                    int v;
                    for (re int i=head[u];i;i=e[i].nxt) {
                        if (e[i].v==fa[u]) continue;
                        int l=st[e[i].v],r=ed[e[i].v];
                        if (l<=st[rt]&&st[rt]<=r) { v=e[i].v; break; }
                    }
                    printf("%d\n",min(query(1,1,n,1,st[v]-1),
                                      query(1,1,n,ed[v]+1,n)));
                }
            }
        }
    }
    return 0;
}
最后修改:2019 年 10 月 17 日 10 : 24 PM