「bzoj3306」树 - Dfs序 | Bill Yang's Blog

「bzoj3306」树 - Dfs序

题目大意

    给定一棵大小为$n$的有根点权树,支持以下操作:

  • 换根
  • 修改点权
  • 查询子树最小值

题目分析

注意这道题并没有树的形态的大幅度修改,仅仅是换根操作。
如果直接上LCT就太暴力且不好做。

考虑展开为Dfs序,查询子树最小值就很简单了。
对于换根怎么办呢,记录根的位置,如果询问的点$x$是$root$的祖先,那么转化为求子树外的最小值。
倍增向上找LCA的时候返回最接近LCA的最后一个点即可。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int min(int a,int b) {
return a<b?a:b;
}
const int maxn=100005;
struct Tree {
int left,right,min;
Tree(int l=0,int r=0,int m=0x7fffffff/2):left(l),right(r),min(m) {}
};
struct Segment_Tree {
Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right,int* a) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index].min=a[Left];
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid,a);
build(rs,mid+1,Right,a);
push_up(index);
}
void push_up(int index) {
tree[index].min=min(tree[ls].min,tree[rs].min);
}
void modify(int index,int target,int v) {
if(target>tree[index].right||target<tree[index].left)return;
if(tree[index].left==tree[index].right) {
tree[index].min=v;
return;
}
modify(ls,target,v);
modify(rs,target,v);
push_up(index);
}
int query(int index,int Left,int Right) {
if(Left>tree[index].right||Right<tree[index].left)return 0x7fffffff/2;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].min;
return min(query(ls,Left,Right),query(rs,Left,Right));
}
} st;
int n,q,step=0,root=1,a[maxn],b[maxn],p[maxn][25],First[maxn],Last[maxn],Depth[maxn];
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs(int Now,int fa,int depth) {
First[Now]=++step;
b[step]=a[Now];
Depth[Now]=depth;
p[Now][0]=fa;
for(int j=1; j<=log2(n); j++)
if(~p[Now][j-1])p[Now][j]=p[p[Now][j-1]][j-1];
for(int Next:edges[Now])Dfs(Next,Now,depth+1);
Last[Now]=step;
}
int LCA(int x,int y,int& pos) {
if(Depth[x]<Depth[y])swap(x,y);
int k=log2(Depth[x]);
for(int i=k; i>=0; i--)
if(Depth[x]-(1<<i)>Depth[y])x=p[x][i];
if(p[x][0]==y) {
pos=x;
return y;
}
for(int i=k; i>=0; i--)
if(~p[x][i]&&p[x][i]!=p[y][i]) {
x=p[x][i];
y=p[y][i];
}
return p[x][0];
}
int main() {
memset(p,-1,sizeof(p));
n=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++) {
int f=Get_Int(),x=Get_Int();
if(f)AddEdge(f,i);
a[i]=x;
}
Dfs(1,-1,1);
st.build(1,1,n,b);
for(int i=1; i<=q; i++) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
if(opt=='V') {
int x=Get_Int(),y=Get_Int();
st.modify(1,First[x],y);
} else if(opt=='E')root=Get_Int();
else {
int x=Get_Int(),pos=0;
if(x==root) {
printf("%d\n",st.tree[1].min);
continue;
}
int lca=LCA(x,root,pos);
if(lca!=x)printf("%d\n",st.query(1,First[x],Last[x]));
else printf("%d\n",min(st.query(1,1,First[pos]-1),st.query(1,Last[pos]+1,n)));
}
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%