Steven_MengのBlog

传送门

本质一样的一道YNOI

首先明确一件事情,这个换根其实是吓你的,

$1.$只有最近的一次换根才会对答案有影响(显然)

$2.$分情况讨论,我们始终以$1$节点为根,设现在查询的节点为$u$,上一次换根的根为$rt$($rt$是一个假的根) ,我们画出$3$个图:

若$u==rt$,显然现在查询的是整棵树,对应到区间$[1,n]$:

若$LCA(u,rt)==u$(或者说$rt$在$u$的子树中),

我们想象一下,把$rt$从底下提上来,查询的就是红色圈圈起来的部分

再把这个红色圈圈起来的部分对应回去

原来就是整棵树去掉$v$的子树的部分,其中$v$为$u$的孩子,$rt$的祖先(可以树上倍增搞一下)

这个可以对应到两个区间$[1,L[v]-1]$,$[R[v]+1,n]$

最后一种情况,若$LCA(u,rt)!=u$,那么我们再画一个图:

发现这个换根和没换一样,所以就是查询区间$[L[u],R[u]]$

所以这道题我们就解决。。。。了吗?

首先,为了准确求出$dfn$ 序,我们要把$dfs2$魔改成这个样子

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs2(int u,int t){
if (!u) return ;
seq[L[u]=++cnt]=u;
top[u]=t;
dfs2(son[u],t);
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v!=son[u]&&v!=fa[u]){
dfs2(v,v);
}
}
R[u]=cnt;
}

然后,这道题还要有一个很孙的特判,如果$u==1||v==1$则返回根节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline int LCA(int u,int v){
if (u==1||v==1) return 1;
if (dep[u]<dep[v]) swap(u,v);
for (register int i=MAXM-1;i>=0;--i){
if (dep[anc[u][i]]>=dep[v]){
u=anc[u][i];
}
}
if (u==v) return u;
for (register int i=MAXM-1;i>=0;--i){
if (anc[u][i]!=anc[v][i]){
u=anc[u][i],v=anc[v][i];
}
}
return anc[u][0];
}

献上$WA$无数次的代码:

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
#define MAXN 200005
#define MAXM 25
using namespace std;
inline 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<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
G[u].push_back(v);
}
int a[MAXN];
int fa[MAXN],dep[MAXN],top[MAXN],sz[MAXN],tofa[MAXN],son[MAXN];
int anc[MAXN][MAXM];
void dfs1(int u,int father){
sz[u]=1;
anc[u][0]=father;
for (register int i=1;i<MAXM;++i){
anc[u][i]=anc[anc[u][i-1]][i-1];
}
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v!=father){
dep[v]=dep[u]+1;
fa[v]=u;
dfs1(v,u);
sz[u]+=sz[v];
if (sz[son[u]]<sz[v]) son[u]=v;
}
}
}
int L[MAXN],R[MAXN],seq[MAXN],cnt;
void dfs2(int u,int t){
if (!u) return ;
seq[L[u]=++cnt]=u;
top[u]=t;
dfs2(son[u],t);
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v!=son[u]&&v!=fa[u]){
dfs2(v,v);
}
}
R[u]=cnt;
}
inline int LCA(int u,int v){
if (u==1||v==1) return 1;
if (dep[u]<dep[v]) swap(u,v);
for (register int i=MAXM-1;i>=0;--i){
if (dep[anc[u][i]]>=dep[v]){
u=anc[u][i];
}
}
if (u==v) return u;
for (register int i=MAXM-1;i>=0;--i){
if (anc[u][i]!=anc[v][i]){
u=anc[u][i],v=anc[v][i];
}
}
return anc[u][0];
}
inline int Hop(int u,int lca){
for (register int i=MAXM-1;i>=0;--i){
if (dep[anc[u][i]]>dep[lca]) {
u=anc[u][i];
}
}
return u;
}
int val[MAXN];
namespace SegmentTree{
struct node{
int l,r;
int mino,tag;
}tree[MAXN<<1];
#define lc i<<1
#define rc i<<1|1
inline void Cover(int i,int val){
tree[i].mino=tree[i].tag=val;
}
inline void pushup(int i){
tree[i].mino=min(tree[lc].mino,tree[rc].mino);
}
inline void pushdown(int i){
if (tree[i].tag!=-1){
Cover(lc,tree[i].tag);
Cover(rc,tree[i].tag);
tree[i].tag=-1;
}
}
void Build(int i,int l,int r){
tree[i].l=l,tree[i].r=r;
tree[i].tag=-1;
if (l==r){
tree[i].mino=a[seq[l]];
return ;
}
int mid=(l+r)>>1;
Build(lc,l,mid);
Build(rc,mid+1,r);
pushup(i);
}
void Update(int i,int L,int R,int val){
if (L<=tree[i].l&&tree[i].r<=R){
Cover(i,val);
return ;
}
int mid=(tree[i].l+tree[i].r)>>1;
pushdown(i);
if (L<=mid) Update(lc,L,R,val);
if (mid<R) Update(rc,L,R,val);
pushup(i);
}
int Query(int i,int L,int R){
if (L<=tree[i].l&&tree[i].r<=R){
return tree[i].mino;
}
int mid=(tree[i].l+tree[i].r)>>1,ans=0x7fffffff;
pushdown(i);
if (L<=mid) ans=min(ans,Query(lc,L,R));
if (mid<R) ans=min(ans,Query(rc,L,R));
return ans;
}
}
using namespace SegmentTree;
inline void UpdateChain(int u,int v,int val){
while (top[u]!=top[v]){
if (dep[top[u]]<dep[top[v]]) swap(u,v);
Update(1,L[top[u]],L[u],val);
u=anc[top[u]][0];
}
if (dep[u]>dep[v]) swap(u,v);
Update(1,L[u],L[v],val);
}
int main(){
int n=read(),m=read();
for (register int i=1;i<n;++i){
int u=read(),v=read();
AddEdge(u,v);
AddEdge(v,u);
}
for (register int i=1;i<=n;++i){
a[i]=read();
}
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
int rt=read();
while (m--){
int opr=read();
if (opr==1){
rt=read();
}
else if (opr==2){
int u=read(),v=read(),val=read();
UpdateChain(u,v,val);
}
else if (opr==3){
int u=read();
if (u==rt){
printf("%d\n",Query(1,1,n));
}
else if (LCA(u,rt)==u){
int v=Hop(rt,u);
printf("%d\n",min(Query(1,1,L[v]-1),Query(1,R[v]+1,n)));
}
else {
printf("%d\n",Query(1,L[u],R[u]));
}
}
}
}

 评论