#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
const int K = 18;
int n, a[N], k, lca[N], vis[N];
int up[N][K], tin[N], tout[N], timer;
vector<int> g[N], t[N], rev[N], c[N];
vector<int> ord;
bool anc(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int LCA(int a, int b) {
if (anc(a, b))
return a;
else if (anc(b, a))
return b;
for (int i = K - 1;i >= 0;i--) {
if (!anc(up[a][i], b) && up[a][i] > 0)
a = up[a][i];
}
return up[a][0];
}
void dfs(int v, int p) {
up[v][0] = p;
tin[v] = ++timer;
for (int i = 1;i < K;i++)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto u : t[v]) {
if (u == p)
continue;
dfs(u, v);
}
tout[v] = timer;
}
void dfs1(int v) {
if (vis[v])
return;
vis[v] = 1;
for (auto u : g[v]) {
dfs1(u);
}
ord.push_back(v);
}
int sz = 0;
void dfs2(int v) {
if (vis[v])
return;
vis[v] = 1;
sz++;
for (auto u : rev[v])
dfs2(u);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> k;
for (int i = 1;i <= n - 1;i++) {
int a, b;
cin >> a >> b;
t[a].push_back(b);
t[b].push_back(a);
}
for (int i = 1;i <= n;i++) {
cin >> a[i];
c[a[i]].push_back(i);
}
dfs(1, 0);
for (int i = 1;i <= k;i++) {
assert(c[i].size() > 0);
lca[i] = c[i][0];
for (int j = 1;j < (int)c[i].size();j++)
lca[i] = LCA(lca[i], c[i][j]);
}
for (int i = 1;i <= n;i++) {
if (i == lca[a[i]])
continue;
if (a[i] != a[up[i][0]]) {
g[a[i]].push_back(a[up[i][0]]);
rev[a[up[i][0]]].push_back(a[i]);
}
}
for (int i = 1;i <= n;i++) {
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
sort(rev[i].begin(), rev[i].end());
rev[i].erase(unique(rev[i].begin(), rev[i].end()), rev[i].end());
}
int ans = 1e9;
for (int i = 1;i <= k;i++) {
if (!vis[i])
dfs1(i);
}
for (int i = 1;i <= n;i++)
vis[i] = 0;
reverse(ord.begin(), ord.end());
for (auto u : ord) {
if (!vis[u]) {
sz = 0;
dfs2(u);
if (sz == 1) {
if (!g[u].empty())
ans = min(ans, (int)g[u].size());
else
ans = 0;
}
else
ans = min(ans, sz - 1);
}
}
cout << ans;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
25176 KB |
Output is correct |
| 2 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
7 ms |
25436 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
25176 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
25176 KB |
Output is correct |
| 2 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
7 ms |
25436 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
25176 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
245 ms |
81064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
25176 KB |
Output is correct |
| 2 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
7 ms |
25436 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
25176 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
