描述
给定一棵大小为 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 ,输出子树最小值。
样例输入
3 7
0 1
1 2
1 3
Q 1
V 1 6
Q 1
V 2 5
Q 1
V 3 4
Q 1
样例输出
1
2
3
4
提示
对于 100% 的数据:n, Q ≤ 10^5。
题解
对于换根操作，如果询问点为\(root\),相当于整棵子树的答案
若询问点不为\(root\)祖先，则相当于以\(1\)为根的子树
若询问点是\(root\)的祖先，那么对于点\(y\)的询问相当于询问除去含\(root\)的子树的最小值，\(dfs\)序则为序列的两段
用树剖+线段树+LCA维护即可
代码
#include<bits/stdc++.h>
#define N 100005
#define inf 0x7fffffff
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (t[p].l+t[p].r>>1)
#define T pair<int,int>
#define mp make_pair
#define il inline
#define vo void
#define in read()
using namespace std;
inline int read()
{
int data=0,w=1;char ch=getchar();
while(ch!=‘-‘&& (ch<‘0‘||ch>‘9‘)) ch=getchar();
if(ch==‘-‘) w=-1,ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘) data=(data<<3)+(data<<1)+ch-‘0‘,ch=getchar();
return data*w;
}
int n,q;
vector<int> e[N];
int first[N],cnt;
il vo add(int s,int fa) {e[fa].push_back(s);}
int siz[N],hson[N],dep[N],fa[N];
int num[N],top[N],pred[N],idx;
int a[N],root=1;
il char gc()
{
char c=getchar();
while(c==‘ ‘||c==‘\n‘||c==‘\r‘)c=getchar();
return c;
}
vo dfs1(int u)
{
siz[u]=1;hson[u]=0;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
dep[v]=dep[u]+1;fa[v]=u;
dfs1(v);
siz[u]+=siz[v];
if(siz[hson[u]]<siz[v]) hson[u]=v;
}
}
vo dfs2(int u,int tp)
{
int son;
top[u]=tp;num[u]=++idx;pred[idx]=u;
if(hson[u]) dfs2(hson[u],tp);
for(int i=0;i<e[u].size();i++)
if(hson[u]!=e[u][i])
dfs2(e[u][i],e[u][i]);
}
struct tree{
int l,r,minn;
}t[N<<2];
il vo pushup(int p){t[p].minn=min(t[lc].minn,t[rc].minn);}
il vo build(int p,int l,int r)
{
t[p].l=l;t[p].r=r;
if(l==r) {t[p].minn=a[pred[l]];return ;}
build(lc,l,mid);build(rc,mid+1,r);
pushup(p);
}
il vo update(int p,int pos,int v)
{
if(t[p].l==t[p].r){t[p].minn=v;return ;}
if(pos<=mid) update(lc,pos,v);
else update(rc,pos,v);
pushup(p);
}
il int query(int p,int ql,int qr)
{
if(ql>t[p].r||qr<t[p].l) return inf;
if(t[p].l>=ql&&t[p].r<=qr) return t[p].minn;
int ret=inf;
if(ql<=mid) ret=min(query(lc,ql,qr),ret);
if(qr>mid) ret=min(query(rc,ql,qr),ret);
return ret;
}
il T lca(int x,int y)
{
int ch=0;int tx=top[x],ty=top[y];
while(tx!=ty)
{
if(dep[tx]<dep[ty]) swap(x,y),swap(tx,ty);
if(fa[tx]==y) ch=tx;
x=fa[tx],tx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
return mp(x,ch?ch:hson[x]);
}
il int qm(int x)
{
if(x==root) return t[1].minn;
T Lca=lca(x,root);int ch=Lca.second;
if(Lca.first!=x) return query(1,num[x],num[x]+siz[x]-1);
else return min(query(1,1,num[ch]-1),query(1,num[ch]+siz[ch],n));
}
int main()
{
n=in,q=in;
for(int i=1;i<=n;i++) add(i,in),a[i]=in;
dfs1(1); dfs2(1,1); build(1,1,n);
int u=0;
while(q--)
{
switch(gc())
{
case ‘V‘:u=in;update(1,num[u],in);break;
case ‘E‘:root=read();break;
case ‘Q‘:printf("%d\n",qm(in));break;
}
}
return 0;
}