给定一棵大小为 n 的有根点权树,支持以下操作:
　　• 换根
　　• 修改点权 
    　• 查询子树最小值 

　　第一行两个整数 n, Q ,分别表示树的大小和操作数。
　　接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f < i。如 果f = 0,那么i为根。输入数据保证只有i = 1时,f = 0。
　　接下来 m 行,为以下格式中的一种:
　　• V x y表示把点x的权改为y
　　• E x 表示把有根树的根改为点 x
　　• Q x 表示查询点 x 的子树最小值 

　　对于每个 Q ,输出子树最小值。 

　　对于 100% 的数据:n, Q ≤ 10^5。

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int read() {     int x=0,f=1; char ch=getchar();     while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}     while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}     return x*f; }  #define MAXN 100010 int N,Q,val[MAXN]; struct EdgeNode{int next,to;}edge[MAXN<<1]; int head[MAXN],cnt; void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;} void InsertEdge(int u,int v) {if (u==0) return; AddEdge(u,v); AddEdge(v,u);} int pl[MAXN],dfn,pr[MAXN],dfsn[MAXN],deep[MAXN],father[MAXN][21],root; void DFS(int now,int last) {     pl[now]=++dfn; dfsn[dfn]=now;     for (int i=1; i<=20; i++)         if (deep[now]>=(1<<i))             father[now][i]=father[father[now][i-1]][i-1];         else             break;     for (int i=head[now]; i; i=edge[i].next)         if (edge[i].to!=last)             {                 deep[edge[i].to]=deep[now]+1;                 father[edge[i].to][0]=now;                 DFS(edge[i].to,now);             }     pr[now]=dfn; } int LCA(int x,int y) {     if (deep[x]<deep[y]) swap(x,y);     int dd=deep[x]-deep[y];     for (int i=0; i<=20; i++)         if (dd&(1<<i)) x=father[x][i];     for (int i=20; i>=0; i--)         if (father[x][i]!=father[y][i])             x=father[x][i],y=father[y][i];     if (x==y) return x; else return father[x][0]; } struct SegmentTreeNode{int l,r,minn;}tree[MAXN<<2]; inline void Update(int now) {tree[now].minn=min(tree[now<<1].minn,tree[now<<1|1].minn);} void BuildTree(int now,int l,int r) {     tree[now].l=l; tree[now].r=r;     if (l==r) {tree[now].minn=val[dfsn[l]]; return;}     int mid=(l+r)>>1;     BuildTree(now<<1,l,mid);     BuildTree(now<<1|1,mid+1,r);     Update(now); } void Change(int now,int pos,int D) {     int l=tree[now].l,r=tree[now].r;     if (l==r) {tree[now].minn=D; return;}     int mid=(l+r)>>1;     if (pos<=mid) Change(now<<1,pos,D);         else Change(now<<1|1,pos,D);     Update(now); } int Query(int now,int L,int R) {     if (R<L) return 0x7fffffff;     int l=tree[now].l,r=tree[now].r;     if (L==l && R==r) return tree[now].minn;     int mid=(l+r)>>1,re=0x7fffffff;     if (R<=mid) return Query(now<<1,L,R);         else if (L>mid) return Query(now<<1|1,L,R);             else return min(Query(now<<1,L,mid),Query(now<<1|1,mid+1,R));     return re; } void ChangeRoot(int x)  {root=x;} int GetAns(int x) {     int lca=LCA(root,x);     if (x==root) return Query(1,1,N);     if (pl[x]<=pl[root] && pr[x]>=pr[root])          {             int dd=deep[root]-deep[x]-1,y=root;             for (int i=0; i<=20; i++)                 if (dd&(1<<i)) y=father[y][i];             return min(Query(1,1,pl[y]-1),Query(1,pr[y]+1,dfn));         }     return Query(1,pl[x],pr[x]); } int main() {     N=read(); Q=read();     for (int fa,i=1; i<=N; i++) fa=read(),InsertEdge(fa,i),val[i]=read();     DFS(1,0);  root=1;     BuildTree(1,1,dfn);     while (Q--)         {             char opt[10]; scanf("%s",opt+1);             int x,y;             switch (opt[1])                 {                     case ‘V‘ : x=read(),y=read(); Change(1,pl[x],y); break;                     case ‘E‘ : x=read(); ChangeRoot(x); break;                     case ‘Q‘ : x=read(); printf("%d\n",GetAns(x)); break;                 }         }     return 0; }