#include <bits/stdc++.h>
using namespace std;
int p[500005][20];
int dep[500005];
vector<int> adjl[500005];
void dfs(int node, int pa){
p[node][0] = pa;
for (auto x : adjl[node]){
if (x==pa) continue;
dep[x] = dep[node]+1;
dfs(x,node);
}
}
int lca(int a, int b){
if (dep[a]>dep[b]){
swap(a,b);
}
int t = dep[b]-dep[a];
for (int x = 0; x<20; x++){
if (t&(1<<x)){
b = p[b][x];
}
}
if (a==b) return a;
for (int x = 19; x>=0; x--){
if (p[a][x]!=p[b][x]){
a = p[a][x];
b = p[b][x];
}
}
return p[a][0];
}
int arr[500005];
vector<int> states[500005];
int pa[500005];
int rt(int a){return pa[a]==a?a:pa[a]=rt(pa[a]);}
void mer(int a, int b){
a = rt(a);
b = rt(b);
if (a==b) return;
pa[a] = b;
}
void dfs2(int node, int np, int val){
val += arr[node];
for (auto x : adjl[node]){
if (x==np) continue;
//printf("node %d, val %d\n",node,val);
if (val>0){
mer(node,x);
}
dfs2(x,node,val);
}
}
vector<int> adjl2[500005];
int main(){
int n,k;
scanf("%d%d",&n,&k);
for (int x = 0; x<n-1; x++){
int a,b;
scanf("%d%d",&a,&b);
adjl[a].push_back(b);
adjl[b].push_back(a);
}
dfs(1,0);
for (int x = 1; x<20; x++){
for (int y = 0; y<=n; y++){
p[y][x] = p[p[y][x-1]][x-1];
}
}
for (int x = 1; x<=n; x++){
int a;
scanf("%d",&a);
states[a].push_back(x);
}
for (int x = 1; x<=k; x++){
if (states[x].empty()) continue;
int cur = states[x][0];
for (int y = 1; y<states[x].size(); y++){
arr[cur]--;
arr[states[x][y]]--;
int t = lca(cur,states[x][y]);
//printf("lca = %d\n",t);
arr[t]+=2;
cur = states[x][y];
}
}
for (int x = 0; x<=n; x++){
pa[x] = x;
}
dfs2(1,0,0);
int z = 0;
for (int x = 2; x<=n; x++){
if (rt(p[x][0])!=rt(x)){
adjl2[rt(x)].push_back(rt(p[x][0]));
adjl2[rt(p[x][0])].push_back(rt(x));
z++;
//printf("z %d %d\n",rt(x),rt(p[x][0]));
}
}
if (z==0){
printf("0");
return 0;
}
int t2 = 0;
for (int x = 1; x<=n; x++){
if (adjl2[x].size()==1){
t2++;
}
}
printf("%d",(t2+1)/2);
}
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int y = 1; y<states[x].size(); y++){
| ~^~~~~~~~~~~~~~~~~
mergers.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d%d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~
mergers.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
mergers.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d",&a);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
35540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
35540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
35540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
48820 KB |
Output is correct |
| 2 |
Correct |
104 ms |
54268 KB |
Output is correct |
| 3 |
Incorrect |
21 ms |
35924 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
35540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
