Description
给定一棵大小为 n 的有根点权树,支持以下操作:
• 换根
• 修改点权
• 查询子树最小值
Solution
单点修改子树查询的话可以想到用dfs序+线段树来处理，换根的处理画一画图应该可以明白：
如果查询的x是当前的根rt，直接返回整棵树的min
如果rt在x的子树中，用倍增的方法找到离x最近的rt的祖先t，整棵树除t的子树以外的部分就是x当前根下的子树
如果rt不在x的子树中，查询x原来的子树的min值
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #define MAXN 100005 #define INF 0x3f3f3f3f using namespace std; int n,q,head[MAXN],cnt=0,rt=0,w[MAXN],p[MAXN][20],deep[MAXN]; int a[MAXN],in[MAXN],out[MAXN],dfn_clock=0; struct Node1 { int l,r,minn; }t[MAXN*4]; struct Node2 { int next,to; }Edges[MAXN*2]; void addedge(int u,int v) { Edges[++cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v; } int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } void dfs(int u) { a[++dfn_clock]=u;in[u]=dfn_clock; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==p[u][0])continue; deep[v]=deep[u]+1;dfs(v); } out[u]=dfn_clock; } void init() { for(int i=1;i<=16;i++) { for(int j=1;j<=n;j++) p[j][i]=p[p[j][i-1]][i-1]; } } void build(int idx,int l,int r) { t[idx].l=l,t[idx].r=r; if(l==r){t[idx].minn=w[a[l]];return;} int mid=(l+r)>>1; build(idx<<1,l,mid),build(idx<<1|1,mid+1,r); t[idx].minn=min(t[idx<<1].minn,t[idx<<1|1].minn); } void change(int idx,int p,int v) { if(t[idx].l==t[idx].r){t[idx].minn=v;return;} int mid=(t[idx].l+t[idx].r)>>1; if(p<=mid)change(idx<<1,p,v); else change(idx<<1|1,p,v); t[idx].minn=min(t[idx<<1].minn,t[idx<<1|1].minn); } int query(int idx,int l,int r) { if(l>r)return INF; if(l<=t[idx].l&&r>=t[idx].r)return t[idx].minn; int mid=(t[idx].l+t[idx].r)>>1; if(r<=mid)return query(idx<<1,l,r); else if(l>mid)return query(idx<<1|1,l,r); else return min(query(idx<<1,l,r),query(idx<<1|1,l,r)); } int main() { memset(head,-1,sizeof(head)); n=read(),q=read(); for(int i=1;i<=n;i++) { p[i][0]=read(),w[i]=read(); if(!p[i][0])rt=i; addedge(p[i][0],i); } dfs(rt),init(); build(1,1,n); for(int i=1;i<=q;i++) { char opt[2];int x,y; scanf("%s",opt); if(opt[0]=='V') x=read(),y=read(),change(1,in[x],y); else if(opt[0]=='E') {x=read();rt=x;} else { x=read(); if(x==rt)printf("%d ",query(1,1,n)); else if(in[rt]>=in[x]&&out[rt]<=out[x]) { int f=deep[rt]-deep[x]-1,t=rt; for(int j=0;j<=18;j++) if(f&(1<<j))t=p[t][j]; printf("%d ",min(query(1,1,in[t]-1),query(1,out[t]+1,n))); } else printf("%d ",query(1,in[x],out[x])); } } return 0; }