题目
[BZOJ3306] 树
样例输入:
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
数据范围
\({n,Q \leq 10^5}\)
分析
\(\color{skyblue}{1}\)
这道题如果没有操作换根
那她就是一道板得不能再板的一道板子题
但是
\(\color{red}{\large 没有如果！}\)
所以这道题她就非常的友[cao]爱[dan]
各种全军覆没↓
\(\color{skyblue}{2}\)
由题意
初始rt(root)=1
所以我们以1为根dfs并建立倍增数组
修改点权就是板子 没什么好说的
如果根换成了rt，要查询x子树内的最小值
那么我们需要分情况讨论：
1）若\({x=rt}\) 则直接输出整棵树的最小值
2）若\({LCA(x,rt) \neq x}\)那么直接输出\({x}\)的子树内的最小值
3）若\({LCA(x,rt)=x}\)那么我们可以把她倒过来看 整棵树除了\({x}\)向下走可以到达\({rt}\)的子树之外全部成了\({x}\)在\({rt}\)为根下的子树，我们把这棵子树中最接近\({x}\)的节点\({y}\)求出，在整个区间中除去\({y}\)在\({1}\)根下子树的范围即可得到答案。
code
Elaina's code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define INF 1000000000
#define mst(a,b) memset(a,b,sizeof(a))
#define Elaina 0
#define lid (id<<1)
#define rid (id<<1|1)
const int N = 1000100;
int read(){
int a=0;
char x=getchar();
while(x<'0'||x>'9')x=getchar();
while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();
return a;
}
int n,m,rt;
int head[N],v[N],xv[N],tot,cnt,in[N],out[N],a[N],dep[N],f[N][30];
struct EDGE{
int nxt,to;
}e[N*2];
struct seg_TREE{
int l,r,minn;
}tr[N*4];
void build(int id,int l,int r){
tr[id].l=l;
tr[id].r=r;
if(l==r){
tr[id].minn=xv[l];
return;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
tr[id].minn=min(tr[lid].minn,tr[rid].minn);
}
void changemin(int id,int x,int k){
if(tr[id].l==tr[id].r){
tr[id].minn=k;
return;
}
int m=(tr[id].l+tr[id].r)>>1;
if(x<=m)
changemin(lid,x,k);
else
changemin(rid,x,k);
tr[id].minn=min(tr[lid].minn,tr[rid].minn);
return;
}
int askmin(int id,int l,int r){
if(l>r){
return INF;
}
if(tr[id].l>=l&&tr[id].r<=r){
return tr[id].minn;
}
int mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid){
return askmin(lid,l,r);
}
if(l>mid){
return askmin(rid,l,r);
}else{
return min(askmin(lid,l,mid),askmin(rid,mid+1,r));
}
}
void add_1(int u,int v){
e[++tot].to=v;
e[tot].nxt=head[u];
head[u]=tot;
}
void dfs(int x,int fa){
xv[++cnt]=a[x];
in[x]=cnt;
dep[x]=dep[fa]+1;
f[x][0]=fa;
for(int j=1;j<30;j++){
f[x][j]=f[f[x][j-1]][j-1];
}
for(int i=head[x];i;i=e[i].nxt){
int k=e[i].to;
if(k!=fa){
dfs(k,x);
}
}
out[x]=cnt;
}
signed main(){
n=read(),m=read();
int x,y;
for(int i=1;i<=n;i++){
x=read(),a[i]=read();
add_1(x,i);
}
rt=1;
dep[0]=0;
dfs(rt,0);
// printf("%lld\n",cnt);
// for(int i=1;i<=n;i++){
// printf("%lld ",xv[i]);
// }
// cout<<"\n";
build(1,1,n);
char s;
for(int i=1;i<=m;i++){
cin>>s;
if(s=='E'){
x=read();
rt=x;
}else if(s=='V'){
x=read(),y=read();
changemin(1,in[x],y);
}else{
x=read();
if(x==rt){
printf("%lld\n",tr[1].minn);
}else if(in[x]<=in[rt]&&out[x]>=out[rt]){
int d=dep[rt]-dep[x]-1,y=rt;
for(int i=0;i<30;i++){
if(d&(1<<i)){
y=f[y][i];
}
}
printf("%lld\n",min(askmin(1,1,in[y]-1),askmin(1,out[y]+1,n)));
}else{
// printf("%lld %lld\n",in[x],out[x]);
printf("%lld\n",askmin(1,in[x],out[x]));
}
}
}
return Elaina;
}
/*
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
5 1000
0 1
1 2
1 3
2 4
2 5
Q 1
E 4
Q 1
*/
都看到这了，真的不点个赞吗(>ω<*)