Lvat_s Blog

和我做过的另外一个BZOJ题很像，但是忘了题号了……BZOJ3306 题解

换根就是针对当前根找到子树然后容斥一下

注意dfs序中一棵树的子树一定是连续的

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,a[N],id[N],pre[N],segn,en,h[N],root,siz[N],son[N],dep[N],fa[N],top[N],OPTION;
 
struct Edge{
int b,next;
}e[N<<1];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int l,r,mn,tag;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag=tree[rt].tag;
    tree[rt<<1|1].tag=tree[rt].tag;
    tree[rt<<1].mn=tree[rt].tag;
    tree[rt<<1|1].mn=tree[rt].tag;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].mn=min(tree[rt<<1].mn,tree[rt<<1|1].mn);
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){tree[rt].mn=a[pre[l]];return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Modify(int rt,int l,int r,int x){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].mn=x;tree[rt].tag=x;return;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Modify(rt<<1,l,r,x);
if(r>mid)Modify(rt<<1|1,l,r,x);
Pushup(rt);
}
 
int Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].mn;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(r<=mid)return Query(rt<<1,l,r);
else if(l>mid)return Query(rt<<1|1,l,r);
else return min(Query(rt<<1,l,r),Query(rt<<1|1,l,r));
}
 
void dfs1(int u,int fat){
siz[u]=1;
dep[u]=dep[fat]+1;
son[u]=0;
fa[u]=fat;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fat)continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(son[u]==v || fa[u]==v)continue;
    dfs2(v,v);
}
}
 
void Change(int x,int y,int v){
int topx=top[x],topy=top[y];
while(topx!=topy){
    if(dep[topx]<dep[topy]){swap(topx,topy);swap(x,y);}
    Modify(1,id[topx],id[x],v);
    x=fa[topx];
    topx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
Modify(1,id[x],id[y],v);
}
 
int Ask(int Id){
if(root==Id)return Query(1,1,n);
int x=root,y=Id,topx=top[x],topy=top[y];
while(topx!=topy){
    if(dep[topx]<dep[topy]){swap(topx,topy);swap(x,y);}
    x=fa[topx];
    topx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=Id)return Query(1,id[Id],id[Id]+siz[Id]-1);
else {
    for(int i=h[Id];i;i=e[i].next){
        int v=e[i].b;
        if(fa[Id]==v)continue;
        if(id[v]<=id[root] && id[root]<=id[v]+siz[v]-1){
            int mn=Query(1,id[1],id[v]-1);
            if(id[v]+siz[v]-1!=n)mn=min(mn,Query(1,id[v]+siz[v],n));
            return mn;
        }
    }
}
}
 
void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
 
int main(){
freopen("3083.in","r",stdin);
freopen("3083.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<n;i++){int u,v;Read(u);Read(v);AddEdge(u,v);AddEdge(v,u);}
for(int i=1;i<=n;i++)Read(a[i]);
Read(root);
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
while(m--){
    int opt,x,y,v;
    Read(opt);
    if(opt==1){Read(x);root=x;}
    if(opt==2){Read(x);Read(y);Read(v);Change(x,y,v);}
    if(opt==3){Read(x);printf("%d\n",Ask(x));}
}
return 0;
}