#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
using namespace std;
set < int > a,b;
set < pair < int , int > > road;
int now=0;
vector < int > Next[500005];
int color[500005];
int deg[500005]={0};
int tt[500005]={0};
int Father[500005]={0};
vector < int > con[500005];
vector < int > use[500005];
int sum[500005]={0};
int M;
int root[500005];
int Find(int here)
{
if(root[here]==here) return root[here];
root[here]=Find(root[here]);
return root[here];
}
void F2(int here,int fa,int xx)
{
for(auto i:Next[here])
{
if(i==fa) continue;
if(root[here]!=root[i])
{
now++;
deg[xx]++;
deg[now]++;
//printf("%d %d %d %d\n",here,i,deg[xx],deg[now]);
F2(i,here,now);
}
else F2(i,here,xx);
}
}
void F4(int here,int fa,int deg)
{
tt[here]=deg;
Father[here]=fa;
for(auto i:Next[here])
{
if(i!=fa)
{
road.insert(make_pair(here,i));
F4(i,here,deg+1);
}
}
}
int LCA(int a,int b)
{
a=root[a];
b=root[b];
if(a==b) return a;
int x,y,t;
if(tt[a]==tt[b])
{
x=Father[a];
y=Father[b];
//printf("aa %d %d\n",x,a);
//printf("bb %d %d\n",y,b);
if(road.find(make_pair(x,a))!=road.end()) road.erase(make_pair(x,a));
if(road.find(make_pair(y,b))!=road.end()) road.erase(make_pair(y,b));
t=LCA(x,y);
root[a]=t;
root[b]=t;
return t;
}
else
{
if(tt[a]<tt[b]) swap(a,b);
x=Father[a];
if(road.find(make_pair(x,a))!=road.end()) road.erase(make_pair(x,a));
t=LCA(x,b);
root[a]=t;
return t;
}
}
int main()
{
int N,K,i,j,x,y,xx=0,ok=1;
scanf("%d %d",&N,&M);
for(i=1;i<N;i++)
{
scanf("%d %d",&x,&y);
Next[x].push_back(y);
Next[y].push_back(x);
}
for(i=1;i<=N;i++)
{
scanf("%d",&color[i]);
root[i]=i;
use[color[i]].push_back(i);
}
F4(1,-1,0);
for(i=1;i<=M;i++)
{
K=use[i].size();
if(K>=2)
{
x=use[i][0];
for(j=1;j<K;j++) x=LCA(x,use[i][j]);
}
}
now=0;
F2(1,-1,0);
for(i=0;i<=now;i++) if(deg[i]==1) xx++;
if(xx==1) printf("0\n");
else printf("%d\n",(xx+1)/2);
return 0;
}
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:89:26: warning: unused variable 'ok' [-Wunused-variable]
89 | int N,K,i,j,x,y,xx=0,ok=1;
| ^~
mergers.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
90 | scanf("%d %d",&N,&M);
| ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
93 | scanf("%d %d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | scanf("%d",&color[i]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
35564 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
35564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
35564 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
35564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
35564 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
35564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
46948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
35564 KB |
Output is correct |
| 2 |
Incorrect |
25 ms |
35564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
