danihao123's Blog

这个题其他操作都不难（DFS序+线段树水过），就是换根有点头疼……直接做的话要TopTree吧。

不过我们考虑用DFS序+线段树的“偷懒”做法。每次查询的时候考虑当前的根，如果这个根最初不在x的子树中，那么对目前的查询值没有影响；如果就是x，那么整个树都是x的子树；如果是x的某个后代，那么整个树里除了他的后代所在额这颗子树以外的所有部分全部变成了x的子树（试着翻转一下就明白了）。判断后代祖先以及在哪个子树这些东西可以用倍增LCA高效实现，问题就这样简单了。

代码：

/**************************************************************
    Problem: 3306
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2308 ms
    Memory:17544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
#define SEG_STD int o,int L,int R
#define MAKE_MID int M=L+(R-L)/2
// #define MAKE_CLD int lc=o<<1,rc=o<<1|1
#define LCH o<<1,L,M
#define RCH o<<1|1,M+1,R
int n;
int minv[maxnode];
int A[maxn];
void maintain(int o){
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(SEG_STD){
    if(L==R){
        minv[o]=A[L];
    }else{
        MAKE_MID;
        build_tree(LCH);
        build_tree(RCH);
        maintain(o);
    }
}
int ql,qr;
int query(SEG_STD){
    if(ql<=L && R<=qr){
        return minv[o];
    }else{
        MAKE_MID;
        int ans=INF;
        if(ql<=M)
            ans=min(ans,query(LCH));
        if(qr>M)
            ans=min(ans,query(RCH));
        return ans;
    }
}
int p,v;
void update(SEG_STD){
    if(L==R){
        minv[o]=v;
    }else{
        MAKE_MID;
        if(p<=M)
            update(LCH);
        else
            update(RCH);
        maintain(o);
    }
}
inline int query(int l,int r){
    if(l<1 || l>n || r<1 || r>n)
        return INF;
    ql=l;
    qr=r;
    return query(1,1,n);
}
inline void update(int pos,int value){
    p=pos;
    v=value;
    update(1,1,n);
}
 
int first[maxn];
int next[maxn],to[maxn];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int d[maxn];
int tid[maxn];
int anc[maxn][19],dep[maxn];
int siz[maxn];
int dfs_clk=0;
void dfs(int x,int fa,int depth){
    dfs_clk++;
    tid[x]=dfs_clk;
    A[dfs_clk]=d[x];
    anc[x][0]=fa;
    dep[x]=depth;
    siz[x]=1;
    int i;
    for(i=first[x];i;i=next[i]){
        dfs(to[i],x,depth+1);
        siz[x]+=siz[to[i]];
    }
}
void process(){
    register int i,j;
    for(j=1;(1<<j)<n;j++)
        for(i=1;i<=n;i++)
            if(anc[i][j-1]!=-1)
                anc[i][j]=anc[anc[i][j-1]][j-1];
}
int root;
bool isAnc(int x){
    register int p=root,j;
    if(dep[p]<dep[x])
        return false;
    for(j=18;j>=0;j--)
        if(dep[p]-(1<<j)>=dep[x] && anc[p][j]!=-1)
            p=anc[p][j];
    return p==x;
}
int findAnc(int x,int y){
    register int j;
    for(j=18;j>=0;j--)
        if(dep[y]-dep[x]-(1<<j)>0 && anc[y][j]!=-1)
            y=anc[y][j];
    return y;
}
 
int getAns(int x){
    if(x==root){
        return query(1,n);
    }else{
        if(isAnc(x)){
            register int t=findAnc(x,root);
            register int l=tid[t],r=tid[t]+siz[t]-1;
            return min(query(1,l-1),query(r+1,n));
        }else{
            return query(tid[x],tid[x]+siz[x]-1);
        }
    }
}
 
int main(){
    int q,x,f;
    register int i;
    char buf[3];
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++){
        scanf("%d%d",&f,&d[i]);
        if(!f){
            root=i;
        }else{
            AddEdge(f,i);
        }
    }
    memset(anc,-1,sizeof(anc));
    dfs(root,-1,0);
    process();
    build_tree(1,1,n);
    while(q--){
        scanf("%s%d",buf,&x);
        if(buf[0]=='V'){
            scanf("%d",&f);
            update(tid[x],f);
        }else{
            if(buf[0]=='Q'){
                printf("%d\n",getAns(x));
            }else{
                root=x;
            }
        }
    }
    return 0;
}

泥萌感觉我还能说什么……

这题就是DFS序套主席树，顺便带上倍增LCA，但有两大坑点：

1. 存放数据不一定要用long long，但输入必须要。
2. 输出数据蛋疼，最后一行行末没回车。

代码：