#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;
template<class T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
#ifdef __APPLE__
#include "debug.h"
#else
#define debug(...) 42
#endif
struct LCA {
vector<int> depth, parent, up;
LCA() {}
LCA(int n) {
depth.resize(n);
parent.resize(n);
up.resize(n);
}
void add_leaf(int v, int par) {
parent[v] = par;
depth[v] = depth[par] + 1;
if (depth[par] - depth[up[par]] == depth[up[par]] - depth[up[up[par]]]) {
up[v] = up[up[par]];
} else {
up[v] = par;
}
}
int la(int v, int k) {
int h = max(depth[v] - k, 0);
while (depth[v] != h) {
if (depth[up[v]] >= h) {
v = up[v];
} else {
v = parent[v];
}
}
return v;
}
int lca(int v, int u) {
if (depth[v] > depth[u]) {
v = la(v, depth[v] - depth[u]);
} else {
u = la(u, depth[u] - depth[v]);
}
while (v != u) {
if (up[v] != up[u]) {
v = up[v];
u = up[u];
} else {
v = parent[v];
u = parent[u];
}
}
return v;
}
};
vector<vector<int>> tr, g, gg;
vector<int> tin, tout, c, ggg;
int timer = 0;
LCA st;
constexpr int LG = 18;
void add(int v, int p) {
g.emplace_back();
ggg[v] = g.size() - 1;
g.back().push_back(c[v]);
gg[0][v] = ggg[p];
for (int i = 1; i < LG; ++i) {
g.emplace_back();
gg[i][v] = g.size() - 1;
g.back().emplace_back(gg[i - 1][v]);
g.back().emplace_back(gg[i - 1][st.la(v, 1 << (i - 1))]);
}
}
void dfs(int v, int p) {
tin[v] = timer++;
if (p == -1) {
g.emplace_back();
ggg[v] = g.size() - 1;
g.back().push_back(c[v]);
}
for (auto u : tr[v]) {
if (u != p) {
st.add_leaf(u, v);
add(u, v);
dfs(u, v);
}
}
tout[v] = timer;
}
vector<int> val;
vector<int> curst;
vector<int> cond, siz;
int cnt = 0;
int k;
int dfs_scc(int j) {
static int timer = 0;
int low = val[j] = ++timer, x;
curst.push_back(j);
for (auto e : g[j]) {
if (cond[e] < 0) {
low = min(low, val[e] ? val[e] : dfs_scc(e));
}
}
if (low == val[j]) {
do {
x = curst.back();
curst.pop_back();
siz[cnt] += (x < k);
cond[x] = cnt;
} while (x != j);
++cnt;
}
return val[j] = low;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#endif
int n;
cin >> n >> k;
tr.resize(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u;
--v;
tr[u].push_back(v);
tr[v].push_back(u);
}
c.resize(n);
cin >> c;
for (auto &i : c) {
--i;
}
tin.resize(n);
tout.resize(n);
st = LCA(n);
g.reserve(LG * n + k);
g.resize(k);
gg.resize(LG, vector<int>(n));
ggg.resize(n);
dfs(0, -1);
vector<vector<int>> cc(k);
for (int i = 0; i < n; ++i) {
cc[c[i]].push_back(i);
}
auto add_edges = [&](int v, int d) {
int cv = c[v];
// for (int i = 0; i < d; ++i) {
// v = st.up[0][v];
// g[cv].push_back(c[v]);
// }
// if (cv == 2) {
// cout << "nigga\n";
// }
for (int i = LG - 1; i >= 0; --i) {
if (d >= (1 << i)) {
g[cv].push_back(gg[i][v]);
d -= (1 << i);
v = st.la(v, (1 << i));
}
}
};
for (int i = 0; i < k; ++i) {
sort(cc[i].begin(), cc[i].end(), [&](int u, int v) {
return tin[u] < tin[v];
});
for (int j = 0; j + 1 < (int) cc[i].size(); ++j) {
int l = st.lca(cc[i][j], cc[i][j + 1]);
add_edges(cc[i][j], st.depth[cc[i][j]] - st.depth[l]);
add_edges(cc[i][j + 1], st.depth[cc[i][j + 1]] - st.depth[l]);
}
}
// for (int i = 0; i < (int) g.size(); ++i) {
// for (int j : g[i]) {
// cout << i + 1 << " " << j + 1 << "\n";
// }
// }
int sz = g.size();
val.resize(sz);
cond.resize(sz, -1);
siz.resize(sz);
for (int i = 0; i < sz; ++i) {
if (cond[i] < 0) {
dfs_scc(i);
}
}
vector<int> iznas(cnt);
for (int i = 0; i < sz; ++i) {
for (auto j : g[i]) {
if (cond[i] != cond[j]) {
++iznas[cond[i]];
}
}
}
// debug(siz);
// debug(iznas);
int ans = INF;
for (int i = 0; i < cnt; ++i) {
if (iznas[i] == 0) {
ans = min(ans, siz[i]);
}
}
cout << ans - 1 << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
360 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
360 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
5 ms |
3284 KB |
Output is correct |
12 |
Correct |
5 ms |
3284 KB |
Output is correct |
13 |
Correct |
5 ms |
3256 KB |
Output is correct |
14 |
Correct |
5 ms |
3284 KB |
Output is correct |
15 |
Correct |
6 ms |
3284 KB |
Output is correct |
16 |
Correct |
6 ms |
3252 KB |
Output is correct |
17 |
Correct |
5 ms |
3328 KB |
Output is correct |
18 |
Correct |
5 ms |
3312 KB |
Output is correct |
19 |
Correct |
6 ms |
3220 KB |
Output is correct |
20 |
Correct |
5 ms |
3284 KB |
Output is correct |
21 |
Correct |
5 ms |
3284 KB |
Output is correct |
22 |
Correct |
6 ms |
3412 KB |
Output is correct |
23 |
Correct |
6 ms |
3668 KB |
Output is correct |
24 |
Correct |
6 ms |
3284 KB |
Output is correct |
25 |
Correct |
8 ms |
3328 KB |
Output is correct |
26 |
Correct |
7 ms |
3284 KB |
Output is correct |
27 |
Correct |
6 ms |
3348 KB |
Output is correct |
28 |
Correct |
6 ms |
3264 KB |
Output is correct |
29 |
Correct |
6 ms |
3216 KB |
Output is correct |
30 |
Correct |
6 ms |
3284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1811 ms |
361016 KB |
Output is correct |
2 |
Correct |
996 ms |
315828 KB |
Output is correct |
3 |
Correct |
1781 ms |
328248 KB |
Output is correct |
4 |
Correct |
974 ms |
315908 KB |
Output is correct |
5 |
Correct |
1753 ms |
356016 KB |
Output is correct |
6 |
Correct |
1006 ms |
315664 KB |
Output is correct |
7 |
Correct |
1696 ms |
343868 KB |
Output is correct |
8 |
Correct |
939 ms |
313556 KB |
Output is correct |
9 |
Correct |
1322 ms |
303352 KB |
Output is correct |
10 |
Correct |
1268 ms |
300864 KB |
Output is correct |
11 |
Correct |
1438 ms |
303876 KB |
Output is correct |
12 |
Correct |
1266 ms |
306340 KB |
Output is correct |
13 |
Correct |
1279 ms |
300496 KB |
Output is correct |
14 |
Correct |
1306 ms |
306720 KB |
Output is correct |
15 |
Correct |
1330 ms |
306144 KB |
Output is correct |
16 |
Correct |
1341 ms |
301300 KB |
Output is correct |
17 |
Correct |
1298 ms |
301644 KB |
Output is correct |
18 |
Correct |
1295 ms |
302128 KB |
Output is correct |
19 |
Correct |
1319 ms |
305148 KB |
Output is correct |
20 |
Correct |
1282 ms |
307736 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
360 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
5 ms |
3284 KB |
Output is correct |
12 |
Correct |
5 ms |
3284 KB |
Output is correct |
13 |
Correct |
5 ms |
3256 KB |
Output is correct |
14 |
Correct |
5 ms |
3284 KB |
Output is correct |
15 |
Correct |
6 ms |
3284 KB |
Output is correct |
16 |
Correct |
6 ms |
3252 KB |
Output is correct |
17 |
Correct |
5 ms |
3328 KB |
Output is correct |
18 |
Correct |
5 ms |
3312 KB |
Output is correct |
19 |
Correct |
6 ms |
3220 KB |
Output is correct |
20 |
Correct |
5 ms |
3284 KB |
Output is correct |
21 |
Correct |
5 ms |
3284 KB |
Output is correct |
22 |
Correct |
6 ms |
3412 KB |
Output is correct |
23 |
Correct |
6 ms |
3668 KB |
Output is correct |
24 |
Correct |
6 ms |
3284 KB |
Output is correct |
25 |
Correct |
8 ms |
3328 KB |
Output is correct |
26 |
Correct |
7 ms |
3284 KB |
Output is correct |
27 |
Correct |
6 ms |
3348 KB |
Output is correct |
28 |
Correct |
6 ms |
3264 KB |
Output is correct |
29 |
Correct |
6 ms |
3216 KB |
Output is correct |
30 |
Correct |
6 ms |
3284 KB |
Output is correct |
31 |
Correct |
1811 ms |
361016 KB |
Output is correct |
32 |
Correct |
996 ms |
315828 KB |
Output is correct |
33 |
Correct |
1781 ms |
328248 KB |
Output is correct |
34 |
Correct |
974 ms |
315908 KB |
Output is correct |
35 |
Correct |
1753 ms |
356016 KB |
Output is correct |
36 |
Correct |
1006 ms |
315664 KB |
Output is correct |
37 |
Correct |
1696 ms |
343868 KB |
Output is correct |
38 |
Correct |
939 ms |
313556 KB |
Output is correct |
39 |
Correct |
1322 ms |
303352 KB |
Output is correct |
40 |
Correct |
1268 ms |
300864 KB |
Output is correct |
41 |
Correct |
1438 ms |
303876 KB |
Output is correct |
42 |
Correct |
1266 ms |
306340 KB |
Output is correct |
43 |
Correct |
1279 ms |
300496 KB |
Output is correct |
44 |
Correct |
1306 ms |
306720 KB |
Output is correct |
45 |
Correct |
1330 ms |
306144 KB |
Output is correct |
46 |
Correct |
1341 ms |
301300 KB |
Output is correct |
47 |
Correct |
1298 ms |
301644 KB |
Output is correct |
48 |
Correct |
1295 ms |
302128 KB |
Output is correct |
49 |
Correct |
1319 ms |
305148 KB |
Output is correct |
50 |
Correct |
1282 ms |
307736 KB |
Output is correct |
51 |
Correct |
1 ms |
212 KB |
Output is correct |
52 |
Correct |
921 ms |
297968 KB |
Output is correct |
53 |
Correct |
931 ms |
297968 KB |
Output is correct |
54 |
Correct |
983 ms |
298076 KB |
Output is correct |
55 |
Correct |
992 ms |
298128 KB |
Output is correct |
56 |
Correct |
968 ms |
297948 KB |
Output is correct |
57 |
Correct |
1072 ms |
298036 KB |
Output is correct |
58 |
Correct |
1482 ms |
300852 KB |
Output is correct |
59 |
Correct |
1259 ms |
304208 KB |
Output is correct |
60 |
Correct |
1533 ms |
304668 KB |
Output is correct |
61 |
Correct |
1462 ms |
300656 KB |
Output is correct |
62 |
Correct |
1029 ms |
315836 KB |
Output is correct |
63 |
Correct |
997 ms |
315824 KB |
Output is correct |
64 |
Correct |
943 ms |
314008 KB |
Output is correct |
65 |
Correct |
984 ms |
315632 KB |
Output is correct |
66 |
Correct |
1275 ms |
300736 KB |
Output is correct |
67 |
Correct |
1217 ms |
301296 KB |
Output is correct |
68 |
Correct |
1064 ms |
300708 KB |
Output is correct |
69 |
Correct |
1197 ms |
300648 KB |
Output is correct |
70 |
Correct |
1232 ms |
300752 KB |
Output is correct |
71 |
Correct |
1119 ms |
300756 KB |
Output is correct |
72 |
Correct |
1129 ms |
300700 KB |
Output is correct |
73 |
Correct |
1192 ms |
301168 KB |
Output is correct |
74 |
Correct |
1146 ms |
300748 KB |
Output is correct |
75 |
Correct |
1167 ms |
300744 KB |
Output is correct |
76 |
Correct |
1244 ms |
302944 KB |
Output is correct |
77 |
Correct |
1193 ms |
302152 KB |
Output is correct |
78 |
Correct |
1419 ms |
301700 KB |
Output is correct |
79 |
Correct |
1443 ms |
299932 KB |
Output is correct |
80 |
Correct |
1386 ms |
307184 KB |
Output is correct |
81 |
Correct |
1357 ms |
303728 KB |
Output is correct |
82 |
Correct |
1334 ms |
303496 KB |
Output is correct |
83 |
Correct |
1377 ms |
300164 KB |
Output is correct |
84 |
Correct |
1442 ms |
306120 KB |
Output is correct |
85 |
Correct |
1317 ms |
304520 KB |
Output is correct |
86 |
Correct |
1436 ms |
299864 KB |
Output is correct |
87 |
Correct |
1389 ms |
301732 KB |
Output is correct |
88 |
Correct |
1699 ms |
303664 KB |
Output is correct |
89 |
Correct |
1659 ms |
299524 KB |
Output is correct |
90 |
Correct |
1590 ms |
299328 KB |
Output is correct |
91 |
Correct |
1591 ms |
301864 KB |
Output is correct |
92 |
Correct |
1648 ms |
300260 KB |
Output is correct |
93 |
Correct |
1635 ms |
299900 KB |
Output is correct |
94 |
Correct |
1478 ms |
299396 KB |
Output is correct |
95 |
Correct |
1508 ms |
301008 KB |
Output is correct |
96 |
Correct |
1602 ms |
299528 KB |
Output is correct |
97 |
Correct |
1703 ms |
301668 KB |
Output is correct |