#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
/* Merger:
first, find out the LCA of all stages
second, for each node find out whether we can cut the edge its father to the node, which can be done by storing every node's stage's LCA
if all its subtree's node's stage's LCA is in its subtree then we can cut it
last, for all the node we can build a virtual tree
we know that if we see the edges between virtual tree's node to node as a stage, the answer won't change
if we merge two stages, then the nodes on the path of the two stages are all uncuttable, so we only have to find out the minimum path cover
and i think it's equal to (the number of leaf (deg == 1) + 1) / 2, done!
guess a few coding will lead us to the ac :happy_mention:
*/
vector<int> e;
struct no{
vector<int> ch,ch2;
int as[21]={0};
int dep=-1;
int md=1e9;
int in=0;
int t;
};
vector<no> v;
vector<int> can;
int cnt=0;
void dfs(int r,int f){
v[r].dep=v[f].dep+1;
v[r].as[0]=f;
v[r].in=cnt;
cnt++;
for(auto h:v[r].ch){
if(h!=f){
dfs(h,r);
}
}
}
void dfs2(int r,int f){
v[r].md=v[e[v[r].t]].dep;
for(auto h:v[r].ch){
if(h!=f){
dfs2(h,r);
v[r].md=min(v[r].md,v[h].md);
}
}
if(r!=f){
if(v[r].md>=v[r].dep){
can.push_back(r);
}
}
}
int lca(int a,int b){
if(v[a].dep<v[b].dep){
swap(a,b);
}
for(int i=20;i>=0;i--){
if(v[v[a].as[i]].dep>=v[b].dep){
a=v[a].as[i];
}
}
if(a==b){
return a;
}
for(int i=20;i>=0;i--){
if(v[a].as[i]!=v[b].as[i]){
a=v[a].as[i];
b=v[b].as[i];
}
}
return v[a].as[0];
}
bool cmp(int a,int b){
return v[a].in<v[b].in;
}
int bvt(vector<int> x,int flag){
sort(x.begin(),x.end(),cmp);
int u=x.size();
for(int i=1;i<u;i++){
x.push_back(lca(x[i],x[i-1]));
}
sort(x.begin(),x.end(),cmp);
if(flag==1){
x.erase(unique(x.begin(),x.end()),x.end());
u=x.size();
for(int i=0;i<u-1;i++){
int z=lca(x[i],x[i+1]);
v[z].ch2.push_back(x[i+1]);
v[x[i+1]].ch2.push_back(z);
}
can=x;
}
return x[0];
}
int main(){
AquA;
int n,k;
cin >> n >> k;
v.resize(n);
e.resize(k);
for(int i=1;i<n;i++){
int a,b;
cin >> a >> b;
a--;
b--;
v[a].ch.push_back(b);
}
dfs(0,0);
for(int i=1;i<21;i++){
for(int j=0;j<n;j++){
v[j].as[i]=v[v[j].as[i-1]].as[i-1];
}
}
vector<vector<int> > gg(k);
for(int i=0;i<n;i++){
int a;
cin >> a;
a--;
v[i].t=a;
gg[a].push_back(i);
}
for(int i=0;i<k;i++){
e[i]=bvt(gg[i],0);
}
dfs2(0,0);
if(!can.size()){
cout << 0 << "\n";
return 0;
}
if(can.size()==1){
cout << 1 << "\n";
return 0;
}
bvt(can,1);
int ans=0;
for(auto h:can){
if(v[h].ch2.size()==1){
ans++;
}
}
cout << (ans+1)/2 << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
17464 KB |
Output is correct |
| 2 |
Incorrect |
82 ms |
22752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
