#include <bits/stdc++.h>
using namespace std;
const int mxn=5e5+5;
int n,par[mxn][22],num[mxn],k,s[mxn],st[mxn],fn[mxn],cnt=0,sz[mxn],comp[mxn],ans=0,cont[mxn];
bool marky[mxn];
struct yall{
int u,uu;
}yal[mxn];
vector<int>v[mxn],act[mxn];
void pre(int z){
st[z]=++cnt;
act[s[z]].push_back(z);
for(int i=1;i<=21;i++)
par[z][i]=par[par[z][i-1]][i-1];
for(auto i:v[z]){
int x=yal[i].u^yal[i].uu^z;
if(par[z][0]!=x){
par[x][0]=z;
pre(x);
}
}
if(act[s[z]].back()==z)num[z]--,cont[s[z]]++;
fn[z]=cnt;
}
int lca(int x,int y){
if(st[x]<=st[y] && fn[x]>=fn[y])return x;
for(int i=21;i>=0;i--){
if(par[x][i]==0)continue;
if(st[par[x][i]]>st[y] || fn[par[x][i]]<st[y])x=par[x][i];
}
return par[x][0];
}
void dfs(int z,int y=0,int sum=0){
if(sum==0)
marky[y]=1;
sum+=num[z];
for(auto i:v[z]){
int x=yal[i].u^yal[i].uu^z;
if(x!=par[z][0]){
dfs(x,i,sum);
}
}
sum-=num[z];
}
void fds(int z){
comp[z]=cnt;
for(auto i:v[z]){
int x=yal[i].u^yal[i].uu^z;
if(!comp[x] && !marky[i])
fds(x);
}
}
int main(){
cin>>n>>k;
for(int i=1;i<n;i++){
cin>>yal[i].u>>yal[i].uu;
v[yal[i].u].push_back(i);
v[yal[i].uu].push_back(i);
}
for(int i=1;i<=n;i++)
cin>>s[i];
pre(1);
for(int i=1;i<=k;i++){
int x=act[i][0];
for(int j=1;j<act[i].size();j++){
x=lca(x,act[i][j]);
}
num[x]+=cont[i];
}
dfs(1);
cnt=1;
for(int i=1;i<=n;i++){
if(!comp[i]){
fds(i);
cnt++;
}
}
for(int i=1;i<n;i++){
if(marky[i]){
sz[comp[yal[i].u]]++;
sz[comp[yal[i].uu]]++;
}
}
for(int i=1;i<=cnt;i++){
if(sz[i]==1)ans++;
}
if(ans==1 || cnt<=2)
cout<<0<<'\n';
else
cout<<(ans+1)/2<<endl;
}
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int j=1;j<act[i].size();j++){
| ~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
33368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
33368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
33368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
95 ms |
49612 KB |
Output is correct |
| 2 |
Correct |
112 ms |
54512 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
33884 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
33368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
