CF342 E. Xenia and Tree
Description
给一棵树，一开始只有1为红，其他点为蓝。两种操作：
- 把一个点染成红点。
- 询问一个点到最近红点的距离。
Solution
数据范围$n\le 10^5,m\le 10^5$，我们不能每一次染色后都去跑一次最短路，所以我们当修改数目达到根号n时去进行一次最短路，查询是如果有点是未更新状态，我们可以通过 $lca$ 来求得两点的距离，这样就可以保证复杂度是$n\sqrt{n} \ log$。
Code
常数略微有点大QWQ1
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
using namespace std;
vector<int> G[MAXN];
int pa[MAXLOGN][MAXN];
int depth[MAXN], dist[MAXN];//dist:到红点最近的距离
int n;
void dfs(int v, int p, int d) {
pa[0][v] = p;
depth[v] = d;
dist[v] = depth[v]-1;
for (int i = 0; i < (int)G[v].size(); i++)
if (G[v][i] != p) dfs(G[v][i], v, d + 1);
}
void init(int V) {
dfs(1, 0, 1);
// cout << "V == " << V << endl;
for (int k = 0; k + 1 < MAXLOGN; k++) {
for (int v = 1; v <= V; v++) {
if (pa[k][v] < 0)
pa[k + 1][v] = -1;
else
pa[k + 1][v] = pa[k][pa[k][v]];
}
}
}
int get(int v, int x) {
for (int k = 0; k < MAXLOGN; k++)
if ((x >> k) & 1) v = pa[k][v];
return v;
}
int lca(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
v = get(v, depth[v] - depth[u]);
if (u == v) return u;
for (int k = MAXLOGN - 1; k >= 0; k--) {
if (pa[k][u] != pa[k][v]) {
u = pa[k][u];
v = pa[k][v];
}
}
return pa[0][u];
}
int dis(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
int q[MAXN],cnt=0, vis[MAXN];
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n , m;
cin >> n >> m;
vis[1] = 1;
for(int i = 1, u , v;i < n; i++){
cin >>u >> v;
G[u].eb(v),G[v].eb(u);
}
init(n);
// dfs(1,0,0);
queue<int> que;
auto solve = [&](){
while(que.size()){
int u = que.front();
// cout << "now === " << u << endl;
que.pop();
for(auto v:G[u]){
if(dist[v]>dist[u]+1){
dist[v]=dist[u]+1;
que.push(v);
}
}
}
};
int base = sqrt(n)+1;
auto update=[&](int x){
// cout << "x === " << x << endl;
if(vis[x])return;
vis[x]=1, dist[x]=0, q[++cnt]=x,que.push(x);
if(cnt==base){
solve();
cnt=0;
}
};
auto query=[&](int x){
int ans = dist[x];
// cout << "ansss == " << ans << endl;
for(int i = 1; i <= cnt; i++){
ans=min(ans,dis(q[i],x));
// cout << "ans == " << ans << endl;
}
return ans;
};
for(int i = 1; i <= m; i++){
int op, x;
cin >> op >> x;
if(op==1){
update(x);
}else {
cout << query(x) << endl;
}
}
}
Description
Solution
Code
1 |
Description
Solution
Code
1 |
Description
Solution
Code
1 |
Description
Solution
Code
1 |