BZOJ3083 遥远的国度

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n,m,t,s,rt,tot,kkk;
int id[MAXN],siz[MAXN],son[MAXN],dep[MAXN],top[MAXN],fa[MAXN],head[MAXN];
long long minn[MAXN<<2],w[MAXN],a[MAXN],tag[MAXN<<2];
struct Edge{int nxt,to;}edge[MAXN<<1];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void add(int from,int to){edge[++t].nxt=head[from],edge[t].to=to,head[from]=t;}
inline void push_up(int x){minn[x]=min(minn[ls(x)],minn[rs(x)]);}
inline void push_down(int x)
{
    if(!tag[x]) return;
    minn[ls(x)]=minn[rs(x)]=tag[x];
    tag[ls(x)]=tag[rs(x)]=tag[x];
    tag[x]=0;
}
inline void build(int x,int l,int r)
{
    if(l==r) {minn[x]=w[l];return;}
    int mid=(l+r)>>1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    push_up(x);
}
inline void update(int x,int l,int r,int ll,int rr,long long k)
{
    if(ll<=l&&r<=rr) 
    {
        minn[x]=tag[x]=k;
        return;
    }
    int mid=(l+r)>>1;
    push_down(x);
    if(ll<=mid) update(ls(x),l,mid,ll,rr,k);
    if(mid<rr) update(rs(x),mid+1,r,ll,rr,k);
    push_up(x);
    
}
inline long long query(int x,int l,int r,int ll,int rr)
{
    if(ll<=l&&r<=rr) return minn[x];
    int mid=(l+r)>>1;
    push_down(x);
    long long cur_ans=2147483648;
    if(ll<=mid) cur_ans=min(cur_ans,query(ls(x),l,mid,ll,rr));
    if(mid<rr)  cur_ans=min(cur_ans,query(rs(x),mid+1,r,ll,rr));
    return cur_ans;
}
inline void dfs1(int now,int pre)
{
    siz[now]=1;
    dep[now]=dep[pre]+1;
    fa[now]=pre;
    int maxx=-1;
    for(int i=head[now];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        dfs1(v,now);
        siz[now]+=siz[v];
        if(siz[v]>maxx) maxx=siz[v],son[now]=v;
    }
}
inline void dfs2(int now,int topf)
{
    id[now]=++tot;
    top[now]=topf;
    w[tot]=a[now];
    if(!son[now]) return;
    dfs2(son[now],topf);
    for(int i=head[now];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==fa[now]||v==son[now]) continue;
        dfs2(v,v);
    }
}
inline void modify(int x,int y,long long k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        update(1,1,n,id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    update(1,1,n,id[x],id[y],k);
}
inline long long solve(int now)
{
    if (now==rt) return query(1,1,n,1,n);
    int x=now,y=rt;
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if (dep[x]<dep[y]) swap(x,y);
    if (now==y)
    {
        for(int i=head[now];i;i=edge[i].nxt)
            if(id[edge[i].to]<=id[rt]&&id[rt]<=id[edge[i].to]+siz[edge[i].to]-1)
        return min(query(1,1,n,1,id[edge[i].to]-1),query(1,1,n,id[edge[i].to]+siz[edge[i].to],n));
    }
    else return query(1,1,n,id[now],id[now]+siz[now]-1);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce3.in","r",stdin);
    freopen("ce.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
        minn[i]=2147483649;
    }
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    scanf("%d",&s),rt=s;
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,x,y;long long k;
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d",&x);
            rt=x;
        }
        else if(op==2)
        {
            scanf("%d%d%lld",&x,&y,&k);
            modify(x,y,k);
        }
        else
        {
            scanf("%d",&x);
            printf("%lld\n",solve(x));
        }
    }
    return 0;
}

BZOJ3083 遥远的国度

原文：https://www.cnblogs.com/fengxunling/p/10242122.html