Submission #899868

#TimeUsernameProblemLanguageResultExecution timeMemory
899868PM1Mergers (JOI19_mergers)C++17
0 / 100
109 ms52312 KiB
#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; 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]--; 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 sum=0,int y=0){ if(sum==0 && z!=1) marky[y]=1; sum+=num[z]; assert(sum>=0); for(auto i:v[z]){ int x=yal[i].u^yal[i].uu^z; if(x!=par[z][0]){ dfs(x,sum,i); } } 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 a=lca(act[i][0],act[i].back()); num[a]++; } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...