Lvat_s Blog

无语了……

参考hzwer的题解，我自己没想出来……

具体就是先搞一遍LCA，再分三种情况判断

详见hzwer题解：传送门

判定ROOT时居然写了if(ROOT=x)简直爆炸

没救了

#include<cstdio>
#include<algorithm>
using namespace std;
 
int h[100005],en,fa[100005][18],data[100005],dfn,L[100005],R[100005],pre[100005],ROOT=1,bits[20],dep[100005],n,q;
 
struct Edge{
int b,next;
}e[200005];
 
struct SegTree{
int l,r,mn;
}tree[400005];
 
void Pushup(int root){
tree[root].mn=min(tree[root*2].mn,tree[root*2+1].mn);
}
 
void Build(int root,int l,int r){
tree[root].l=l;
tree[root].r=r;
if(l==r){
    tree[root].mn=data[pre[l]];
    return;
}
int mid=l+r>>1;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
Pushup(root);
}
 
void Change(int root,int pos,int val){
if(tree[root].l==tree[root].r){
    tree[root].mn=val;
    return;
}
int mid=tree[root].l+tree[root].r>>1;
if(pos<=mid)Change(root*2,pos,val);
if(pos>mid)Change(root*2+1,pos,val);
Pushup(root);
}
 
int GtMn(int root,int l,int r){
if(l>r)return 2100000000;
if(tree[root].l>=l && tree[root].r<=r){
    return tree[root].mn;
}
int mid=tree[root].l+tree[root].r>>1,ans=2100000000;
if(l<=mid)ans=min(ans,GtMn(root*2,l,r));
if(r>mid)ans=min(ans,GtMn(root*2+1,l,r));
return ans;
}
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
void dfs(int u){
L[u]=++dfn;
pre[dfn]=u;
for(int i=1;i<=18;i++){
    if(bits[i]<=dep[u])fa[u][i]=fa[fa[u][i-1]][i-1];
    else break;
}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    dep[v]=dep[u]+1;
    fa[v][0]=u;
    dfs(v);
}
R[u]=dfn;
}
 
int main(){
freopen("3306.in","r",stdin);
freopen("3306.out","w",stdout);
bits[0]=1;
for(int i=1;i<=18;i++)bits[i]=bits[i-1]<<1;
scanf("%d %d",&n,&q);
//printf("%d %d\n",n,q);
for(int i=1;i<=n;i++){
    int u;
    scanf("%d %d",&u,&data[i]);
    //printf("%d %d\n",u,data[i]);
    if(u)AddEdge(u,i);
}
dfs(ROOT=1);
Build(1,1,n);
for(int i=1;i<=q;i++){
    char s[5];
    int x,y;
    scanf("%s",s);
    if(s[0]=='V'){
        scanf("%d %d",&x,&y);
        Change(1,L[x],y);
    }
    if(s[0]=='E'){
        scanf("%d",&x);
        ROOT=x;
    }
    if(s[0]=='Q'){
        scanf("%d",&x);
        if(ROOT==x){printf("%d\n",tree[1].mn);continue;}
        if(L[x]<=L[ROOT] && R[x]>=R[ROOT]){
            y=ROOT;
            int deep=dep[y]-dep[x]-1;
            for(int i=0;i<=18;i++){
                if(bits[i]&deep)y=fa[y][i];
            }
            printf("%d\n",min(GtMn(1,1,L[y]-1),GtMn(1,R[y]+1,n)));
            continue;
        }
        printf("%d\n",GtMn(1,L[x],R[x]));
    }
}
return 0;
}