// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 4e5 + 5, lg = 20;
int n, k;
int up[N][lg], f[N], c[N];
vector<int> adj[N], ver[N];
int h[N], tin[N], tout[N], T;
int par[N];
void dfs(int v, int p) {
par[v] = p;
up[v][0] = p;
for (int i = 1; i < lg; i++)
up[v][i] = up[up[v][i - 1]][i - 1];
tin[v] = ++T;
for (auto u : adj[v]) {
if (u != p) {
h[u] = h[v] + 1;
dfs(u, v);
}
}
tout[v] = T;
}
bool anc(int v, int u) {
return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int lca(int v, int u) {
if (tin[v] > tin[u]) swap(v, u);
if (anc(v, u)) return v;
for (int i = lg - 1; i >= 0; i--)
if (!anc(up[u][i], v))
u = up[u][i];
return up[u][0];
}
vector<int> out[N], in[N];
void dfs2(int v, int p) {
int u = par[v];
while (h[u] > h[f[c[v]]]) {
out[c[v]].pb(c[u]);
in[c[u]].pb(c[v]);
u = par[u];
}
par[v] = u;
if (h[u] >= h[f[c[v]]]) {
out[c[v]].pb(c[f[c[v]]]);
in[c[f[c[v]]]].pb(c[v]);
par[v] = par[f[c[v]]];
}
for (auto u : adj[v]) {
if (u != p)
dfs2(u, v);
}
}
bool vis[N];
int col[N];
vector<int> vec;
void dfs3(int v) {
vis[v] = true;
for (auto u : out[v]) {
if (!vis[u]) dfs3(u);
}
vec.pb(v);
}
vector<int> V;
void dfs4(int v, int x) {
col[v] = x;
for (auto u : in[v]) {
if (!col[u])
dfs4(u, x);
}
V.pb(v);
}
void solve() {
cin >> n >> k;
for (int i = 0; i < n - 1; i++) {
int v, u; cin >> v >> u;
adj[v].pb(u);
adj[u].pb(v);
}
for (int i = 1; i <= n; i++) cin >> c[i], ver[c[i]].pb(i);
dfs(1, 0);
h[0] = -1;
tout[0] = T;
for (int i = 1; i <= k; i++) {
f[i] = ver[i].back();
for (auto v : ver[i])
f[i] = lca(f[i], v);
}
dfs2(1, 0);
for (int i = 1; i <= k; i++) {
if (!vis[i])
dfs3(i);
}
int ans = n + 1;
for (int i = k - 1; i >= 0; i--) {
int w = vec[i];
if (col[w] == 0) {
V.clear();
dfs4(w, w);
bool ok = true;
int cnt = V.size();
for (auto v : V) {
for (auto u : out[v])
ok &= col[u] == col[v];
}
if (ok) ans = min(ans, cnt);
}
}
cout << ans - 1 << '\n';
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1; // cin >> tc;
while (tc--) {
solve();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
47452 KB |
Output is correct |
2 |
Correct |
10 ms |
47664 KB |
Output is correct |
3 |
Correct |
10 ms |
47664 KB |
Output is correct |
4 |
Correct |
10 ms |
47664 KB |
Output is correct |
5 |
Correct |
10 ms |
47452 KB |
Output is correct |
6 |
Correct |
10 ms |
47452 KB |
Output is correct |
7 |
Correct |
9 ms |
47448 KB |
Output is correct |
8 |
Correct |
9 ms |
47448 KB |
Output is correct |
9 |
Correct |
10 ms |
47452 KB |
Output is correct |
10 |
Correct |
10 ms |
49664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
47452 KB |
Output is correct |
2 |
Correct |
10 ms |
47664 KB |
Output is correct |
3 |
Correct |
10 ms |
47664 KB |
Output is correct |
4 |
Correct |
10 ms |
47664 KB |
Output is correct |
5 |
Correct |
10 ms |
47452 KB |
Output is correct |
6 |
Correct |
10 ms |
47452 KB |
Output is correct |
7 |
Correct |
9 ms |
47448 KB |
Output is correct |
8 |
Correct |
9 ms |
47448 KB |
Output is correct |
9 |
Correct |
10 ms |
47452 KB |
Output is correct |
10 |
Correct |
10 ms |
49664 KB |
Output is correct |
11 |
Correct |
11 ms |
47708 KB |
Output is correct |
12 |
Correct |
11 ms |
47584 KB |
Output is correct |
13 |
Correct |
10 ms |
47956 KB |
Output is correct |
14 |
Correct |
10 ms |
47708 KB |
Output is correct |
15 |
Correct |
10 ms |
47628 KB |
Output is correct |
16 |
Correct |
10 ms |
47964 KB |
Output is correct |
17 |
Correct |
10 ms |
47708 KB |
Output is correct |
18 |
Correct |
11 ms |
47740 KB |
Output is correct |
19 |
Correct |
11 ms |
47704 KB |
Output is correct |
20 |
Correct |
10 ms |
47708 KB |
Output is correct |
21 |
Correct |
11 ms |
47708 KB |
Output is correct |
22 |
Correct |
10 ms |
47964 KB |
Output is correct |
23 |
Correct |
10 ms |
47708 KB |
Output is correct |
24 |
Correct |
12 ms |
47708 KB |
Output is correct |
25 |
Correct |
11 ms |
47708 KB |
Output is correct |
26 |
Correct |
11 ms |
47708 KB |
Output is correct |
27 |
Correct |
11 ms |
47704 KB |
Output is correct |
28 |
Correct |
12 ms |
47708 KB |
Output is correct |
29 |
Correct |
11 ms |
47708 KB |
Output is correct |
30 |
Correct |
12 ms |
47704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
200 ms |
96104 KB |
Output is correct |
2 |
Correct |
108 ms |
96636 KB |
Output is correct |
3 |
Correct |
202 ms |
95948 KB |
Output is correct |
4 |
Correct |
108 ms |
96716 KB |
Output is correct |
5 |
Correct |
220 ms |
92620 KB |
Output is correct |
6 |
Correct |
108 ms |
96692 KB |
Output is correct |
7 |
Correct |
199 ms |
92732 KB |
Output is correct |
8 |
Correct |
120 ms |
95608 KB |
Output is correct |
9 |
Correct |
206 ms |
89488 KB |
Output is correct |
10 |
Correct |
211 ms |
86916 KB |
Output is correct |
11 |
Correct |
201 ms |
89804 KB |
Output is correct |
12 |
Correct |
215 ms |
92364 KB |
Output is correct |
13 |
Correct |
197 ms |
86488 KB |
Output is correct |
14 |
Correct |
202 ms |
92632 KB |
Output is correct |
15 |
Correct |
227 ms |
92608 KB |
Output is correct |
16 |
Correct |
192 ms |
87500 KB |
Output is correct |
17 |
Correct |
203 ms |
88160 KB |
Output is correct |
18 |
Correct |
223 ms |
88300 KB |
Output is correct |
19 |
Correct |
201 ms |
91344 KB |
Output is correct |
20 |
Correct |
216 ms |
93648 KB |
Output is correct |
21 |
Correct |
10 ms |
49500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
47452 KB |
Output is correct |
2 |
Correct |
10 ms |
47664 KB |
Output is correct |
3 |
Correct |
10 ms |
47664 KB |
Output is correct |
4 |
Correct |
10 ms |
47664 KB |
Output is correct |
5 |
Correct |
10 ms |
47452 KB |
Output is correct |
6 |
Correct |
10 ms |
47452 KB |
Output is correct |
7 |
Correct |
9 ms |
47448 KB |
Output is correct |
8 |
Correct |
9 ms |
47448 KB |
Output is correct |
9 |
Correct |
10 ms |
47452 KB |
Output is correct |
10 |
Correct |
10 ms |
49664 KB |
Output is correct |
11 |
Correct |
11 ms |
47708 KB |
Output is correct |
12 |
Correct |
11 ms |
47584 KB |
Output is correct |
13 |
Correct |
10 ms |
47956 KB |
Output is correct |
14 |
Correct |
10 ms |
47708 KB |
Output is correct |
15 |
Correct |
10 ms |
47628 KB |
Output is correct |
16 |
Correct |
10 ms |
47964 KB |
Output is correct |
17 |
Correct |
10 ms |
47708 KB |
Output is correct |
18 |
Correct |
11 ms |
47740 KB |
Output is correct |
19 |
Correct |
11 ms |
47704 KB |
Output is correct |
20 |
Correct |
10 ms |
47708 KB |
Output is correct |
21 |
Correct |
11 ms |
47708 KB |
Output is correct |
22 |
Correct |
10 ms |
47964 KB |
Output is correct |
23 |
Correct |
10 ms |
47708 KB |
Output is correct |
24 |
Correct |
12 ms |
47708 KB |
Output is correct |
25 |
Correct |
11 ms |
47708 KB |
Output is correct |
26 |
Correct |
11 ms |
47708 KB |
Output is correct |
27 |
Correct |
11 ms |
47704 KB |
Output is correct |
28 |
Correct |
12 ms |
47708 KB |
Output is correct |
29 |
Correct |
11 ms |
47708 KB |
Output is correct |
30 |
Correct |
12 ms |
47704 KB |
Output is correct |
31 |
Correct |
200 ms |
96104 KB |
Output is correct |
32 |
Correct |
108 ms |
96636 KB |
Output is correct |
33 |
Correct |
202 ms |
95948 KB |
Output is correct |
34 |
Correct |
108 ms |
96716 KB |
Output is correct |
35 |
Correct |
220 ms |
92620 KB |
Output is correct |
36 |
Correct |
108 ms |
96692 KB |
Output is correct |
37 |
Correct |
199 ms |
92732 KB |
Output is correct |
38 |
Correct |
120 ms |
95608 KB |
Output is correct |
39 |
Correct |
206 ms |
89488 KB |
Output is correct |
40 |
Correct |
211 ms |
86916 KB |
Output is correct |
41 |
Correct |
201 ms |
89804 KB |
Output is correct |
42 |
Correct |
215 ms |
92364 KB |
Output is correct |
43 |
Correct |
197 ms |
86488 KB |
Output is correct |
44 |
Correct |
202 ms |
92632 KB |
Output is correct |
45 |
Correct |
227 ms |
92608 KB |
Output is correct |
46 |
Correct |
192 ms |
87500 KB |
Output is correct |
47 |
Correct |
203 ms |
88160 KB |
Output is correct |
48 |
Correct |
223 ms |
88300 KB |
Output is correct |
49 |
Correct |
201 ms |
91344 KB |
Output is correct |
50 |
Correct |
216 ms |
93648 KB |
Output is correct |
51 |
Correct |
10 ms |
49500 KB |
Output is correct |
52 |
Correct |
189 ms |
76988 KB |
Output is correct |
53 |
Correct |
192 ms |
77024 KB |
Output is correct |
54 |
Correct |
193 ms |
76972 KB |
Output is correct |
55 |
Correct |
195 ms |
77148 KB |
Output is correct |
56 |
Correct |
204 ms |
76988 KB |
Output is correct |
57 |
Correct |
187 ms |
77136 KB |
Output is correct |
58 |
Correct |
231 ms |
81392 KB |
Output is correct |
59 |
Correct |
235 ms |
82228 KB |
Output is correct |
60 |
Runtime error |
1333 ms |
524288 KB |
Execution killed with signal 9 |
61 |
Halted |
0 ms |
0 KB |
- |