#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 5e5 + 5;
int n, k, x, y, tin[N], tout[N], timer, up[N][21], pref[N], par[N], ans, m[N], sz[N], deg[N];
vector < vector <int> > g, vec;
void dfs (int v, int p = 0)
{
par[v] = p;
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i < 20; i++)
up[v][i] = up[ up[v][i - 1] ][i - 1];
for (auto to : g[v]){
if (to == p) continue;
dfs(to, v);
}
tout[v] = ++timer;
}
bool upper (int a, int b)
{
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca (int a, int b)
{
if (upper(a, b) ) return a;
if (upper(b, a) ) return b;
for (int i = 19; i >= 0; i--){
if (up[a][i] && !upper(up[a][i], b) )
a = up[a][i];
}
return up[a][0];
}
int get (int v){
return v == m[v] ? v : m[v] = get(m[v]);
}
void unite (int a, int b)
{
a = get(a);
b = get(b);
if (a != b){
if (sz[a] > sz[b]) swap(a, b);
sz[b] += sz[a];
m[a] = b;
deg[b] += deg[a];
}
}
void Dfs (int v, int p = 0)
{
for (auto to : g[v]){
if (to == p) continue;
Dfs(to, v);
pref[v] += pref[to];
}
if (pref[v] > 0 && p){
unite(v, p);
cout << v << endl;
}
else if (p) {
++deg[get(p)];
++deg[get(v)];
}
}
main(){
cin >> n >> k;
g.resize(n + 1);
vec.resize(k + 1);
for (int i = 1; i < n; i++){
scanf("%d%d", &x, &y);
g[x].pb(y);
g[y].pb(x);
}
dfs(1);
for (int i = 1; i <= n; i++){
scanf("%d", &x);
vec[x].pb(i);
m[i] = i;
sz[i] = 1;
}
for (int i = 1; i <= k; i++){
if (vec[i].empty() ) continue;
int LCA = vec[i][0];
for (int j = 1; j < (int)vec[i].size(); j++){
LCA = lca(LCA, vec[i][j]);
}
for (int j = 0; j < (int)vec[i].size(); j++){
pref[ vec[i][j] ]++;
pref[ LCA ]--;
}
}
Dfs(1);
for (int i = 1; i <= n; i++){
if (m[i] == i && deg[i] == 1)
ans++;
}
if (sz[ get(1) ] == n){
puts("0");
}
else{
cout << (ans + 1) / 2 << endl;
}
}
/**
5 4
1 2
2 3
3 4
4 5
1
2
3
4
1
**/
Compilation message
mergers.cpp:81:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
mergers.cpp: In function 'int main()':
mergers.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
281 ms |
19452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
