Bzoj3306: tree (dfn order + line segment tree + multiplication)

Problem

Subtree minimum query that supports root change and modified weight

Solution

Do not consider changing the root is the line segment tree template question.. Then add the roots We found that after changing the root, it has nothing to do with the minimum value of most of the subtrees in the original image. only11The point above the new root will change New root: minimum for all points In addition to the new root, the point on the chain: remove all the other points of the new root... (emmm draw a picture to see) The practice isdfndfnOrder to create a line segment tree... Multiply to find the remaining part of the part to be removed is the answer.

Code

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
#define inf 0x3f3f3f3f
int n,q,num=0,tot=0,root,fa[N][20],d[N],h[N],in[N],out[N],rl[N],mn[N<<2],a[N];
char op[4];
struct node{int to,next;}mp[N];
inline void insert(int x,int y){
    mp[++num].to=y;mp[num].next=h[x];h[x]=num;
}
inline void dfs(int x){
    in[x]=++tot;rl[tot]=x;
    for(int i=1;i<=16;i++){
        if(!fa[x][i-1]) break;
        fa[x][i]=fa[fa[x][i-1]][i-1];
    } 
    for(int i=h[x];i;i=mp[i].next){
        int y=mp[i].to;if(y==fa[x][0]) continue;
        d[y]=d[x]+1;dfs(y);
    }out[x]=tot;
}
inline void update(int v){
    mn[v]=min(mn[v<<1],mn[v<<1|1]);
}
void build(int v,int l,int r){
    if(l==r){
        mn[v]=a[rl[l]];
        return;
    }int mid=l+r>>1;
    build(v<<1,l,mid);build(v<<1|1,mid+1,r);
    update(v);
}
void change(int v,int l,int r,int x,int y){
    if(l==r){
        mn[v]=y;
        return;
    }int mid=l+r>>1;
    if(x<=mid) change(v<<1,l,mid,x,y); 
    else change(v<<1|1,mid+1,r,x,y);
    update(v);
}
int query(int v,int l,int r,int x,int y){
    if(x>y) return inf;
    if(x<=l && r<=y) return mn[v];
    int mid=l+r>>1,res=inf;
    if(x<=mid) res=min(res,query(v<<1,l,mid,x,y));
    if(mid<y) res=min(res,query(v<<1|1,mid+1,r,x,y));
    return res;
}
int main(){
    freopen("a.in","r",stdin);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&fa[i][0],&a[i]);
        if(i!=1) insert(fa[i][0],i);
    }d[1]=1;dfs(1);build(1,1,n);root=1;

    for(int i=1;i<=q;i++){
        int x,y;scanf("%s%d",op,&x);
        if(op[0]=='V'){
            scanf("%d",&y);
            change(1,1,n,in[x],y);
        }else if(op[0]=='Q'){
            if(in[x]<=in[root] && in[root]<=out[x]){
                if(x==root) printf("%d\n",mn[1]);
                else{
                    y=root;
                    for(int j=16;j>=0;j--) if(d[fa[y][j]]>d[x]) y=fa[y][j];
                    printf("%d\n",min(query(1,1,n,1,in[y]-1),query(1,1,n,out[y]+1,n)));
                }
            }else printf("%d\n",query(1,1,n,in[x],out[x]));
        }else root=x;
    }
    return 0;
}