// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
using db = long double;
template<class T> using pq = priority_queue<T, V<T>, less<T>>;
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, K; cin >> N >> K;
V<vi> adj(N), pos(K);
for(int i = 0; i < N - 1; i++) {
int u, v; cin >> u >> v; --u, --v;
adj[u].pb(v); adj[v].pb(u);
}
vi A(N); for(auto& x : A) { cin >> x; --x; }
for(int i = 0; i < N; i++) pos[A[i]].pb(i);
vi proc(N), sub(N), par(N), rt(N), vis(N), seen(K);
function<void(int, int)> gen = [&](int u, int p) {
sub[u] = 1;
for(auto& v : adj[u]) if (!proc[u] && v != p) {
gen(v, u);
sub[u] += sub[v];
}
};
function<void(int, int)> fix = [&](int u, int p) {
par[u] = p; rt[u] = rt[p];
for(auto& v : adj[u]) if (!proc[v] && v != p) fix(v, u);
};
function<int(int, int, int)> find = [&](int u, int p, int n) {
for(auto& v : adj[u]) if (!proc[v] && v != p) {
if (2 * sub[v] > n) return find(v, u, n);
}
return u;
};
int ans = MOD;
function<void(int)> decomp = [&](int u) {
gen(u, u); int c = find(u, -1, sub[u]);
rt[c] = c; fix(c, c);
// cout << "CENTROID: " << c << endl;
vi have;
vis[c] = 1; have.pb(c);
int res = 0;
for(int i = 0; i < sz(have); i++) {
int x = have[i];
// cout << "AT: " << x << endl;
if (!seen[A[x]]) {
++res;
for(auto& y : pos[A[x]]) if (!vis[y]) {
if (rt[y] != c) res = MOD;
have.pb(y); vis[y] = 1;
}
seen[A[x]] = 1;
}
if (!vis[par[x]]) {
have.pb(par[x]);
vis[par[x]] = 1;
}
}
for(auto& x : have) vis[x] = 0, seen[A[x]] = 0;
// cout << "RES: " << res << endl;
ans = min(ans, res);
proc[c] = 1;
for(auto& v : adj[c]) if (!proc[v]) decomp(v);
};
decomp(0);
cout << ans - 1 << nl;
exit(0-0);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
37 ms |
596 KB |
Output is correct |
12 |
Correct |
37 ms |
596 KB |
Output is correct |
13 |
Correct |
36 ms |
596 KB |
Output is correct |
14 |
Correct |
37 ms |
596 KB |
Output is correct |
15 |
Correct |
5 ms |
596 KB |
Output is correct |
16 |
Correct |
5 ms |
596 KB |
Output is correct |
17 |
Correct |
10 ms |
596 KB |
Output is correct |
18 |
Correct |
11 ms |
596 KB |
Output is correct |
19 |
Correct |
10 ms |
596 KB |
Output is correct |
20 |
Correct |
11 ms |
652 KB |
Output is correct |
21 |
Correct |
11 ms |
680 KB |
Output is correct |
22 |
Correct |
10 ms |
724 KB |
Output is correct |
23 |
Correct |
17 ms |
724 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
15 ms |
724 KB |
Output is correct |
26 |
Correct |
14 ms |
972 KB |
Output is correct |
27 |
Correct |
16 ms |
724 KB |
Output is correct |
28 |
Correct |
13 ms |
596 KB |
Output is correct |
29 |
Correct |
12 ms |
596 KB |
Output is correct |
30 |
Correct |
10 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
3013 ms |
57704 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
37 ms |
596 KB |
Output is correct |
12 |
Correct |
37 ms |
596 KB |
Output is correct |
13 |
Correct |
36 ms |
596 KB |
Output is correct |
14 |
Correct |
37 ms |
596 KB |
Output is correct |
15 |
Correct |
5 ms |
596 KB |
Output is correct |
16 |
Correct |
5 ms |
596 KB |
Output is correct |
17 |
Correct |
10 ms |
596 KB |
Output is correct |
18 |
Correct |
11 ms |
596 KB |
Output is correct |
19 |
Correct |
10 ms |
596 KB |
Output is correct |
20 |
Correct |
11 ms |
652 KB |
Output is correct |
21 |
Correct |
11 ms |
680 KB |
Output is correct |
22 |
Correct |
10 ms |
724 KB |
Output is correct |
23 |
Correct |
17 ms |
724 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
15 ms |
724 KB |
Output is correct |
26 |
Correct |
14 ms |
972 KB |
Output is correct |
27 |
Correct |
16 ms |
724 KB |
Output is correct |
28 |
Correct |
13 ms |
596 KB |
Output is correct |
29 |
Correct |
12 ms |
596 KB |
Output is correct |
30 |
Correct |
10 ms |
596 KB |
Output is correct |
31 |
Execution timed out |
3013 ms |
57704 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |