#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define fi first
#define se second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax=5e5+5;
vector<int> adj[nax];
bool sheep[nax];
bool removed[nax];
bool ans[nax];
int sz[nax];
int dep[nax];
int dp[20][nax];
vector<pair<int,int>> parent[nax];
int dis[nax];
int get_size(int x,int p){
sz[x]=1;
for(auto u:adj[x]){
if(u==p||removed[u]) continue;
sz[x]+=get_size(u,x);
}
return sz[x];
}
int get_centroid(int x,int t_sz,int p){
for(auto u:adj[x]){
if(removed[u]||u==p) continue;
if(sz[u]*2>t_sz) return get_centroid(u,t_sz,x);
}
return x;
}
int cur=0;
void get_dist(int x,int p,int centroid){
if(sheep[x]) dis[centroid]=min(dis[centroid],cur);
for(auto u:adj[x]){
if(removed[u]||u==p) continue;
cur++;
get_dist(u,x,centroid);
cur--;
}
parent[x].pb({centroid,cur});
}
void build(int x){
int centroid=get_centroid(x,get_size(x,-1),-1);
get_dist(centroid,-1,centroid);
removed[centroid]=1;
for(auto u:adj[centroid]){
if(removed[u]) continue;
build(u);
}
}
void dfs(int x,int p){
for (int i = 1; i < 20; ++i)
{
dp[i][x]=dp[i-1][dp[i-1][x]];
}
for(auto u:adj[x]){
if(u==p) continue;
dep[u]=dep[x]+1;
dp[0][u]=x;
dfs(u,x);
}
return;
}
int jump(int x,int d){
for (int i = 19; i >= 0; --i)
{
if(d&(1<<i)) x=dp[i][x];
}
return x;
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
x=jump(x,dep[x]-dep[y]);
if(x==y) return x;
for (int i = 19; i >= 0; --i)
{
if(dp[i][x]!=dp[i][y]){
x=dp[i][x];
y=dp[i][y];
}
}
return dp[x][0];
}
bool compare(int x,int y){
return dep[x]<dep[y];
}
signed main(){
iostream::sync_with_stdio(false);
int n,k;
cin>>n>>k;
vector<int> tab(k);
for (int i = 0; i < n; ++i)
{
dis[i]=1e9;
}
for (int i = 0; i < n-1; ++i)
{
int x,y;
cin>>x>>y;
x--;y--;
adj[x].pb(y);
adj[y].pb(x);
}
for (int i = 0; i < k; ++i)
{
int x;
cin>>x;
tab[i]=x-1;
sheep[--x]=true;
}
build(0);
for (int i = 0; i < n; ++i)
{
for(auto u:parent[i]){
dis[i]=min(dis[i],u.se+dis[u.fi]);
}
}
dfs(0,-1);
sort(tab.rbegin(),tab.rend(),compare);
for (int i = 0; i < k; ++i)
{
int l=0;
int r=dep[tab[i]];
while(r-l>1){
int mid=(r+l)/2;
if(dis[jump(tab[i],mid)]==mid) l=mid;
else r=mid;
}
ans[jump(tab[i],l)]=1;
}
vector<int> cnt;
for (int i = 0; i < n; ++i)
{
if(ans[i]==1) cnt.pb(i);
}
cout <<cnt.size()<<endl;
for (int i = 0; i < cnt.size(); ++i)
{
cout <<cnt[i]+1<<" ";
}cout <<endl;
}
Compilation message
pastiri.cpp: In function 'int main()':
pastiri.cpp:141:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for (int i = 0; i < cnt.size(); ++i)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
559 ms |
245844 KB |
Output is correct |
| 2 |
Incorrect |
579 ms |
247040 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
25176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
24408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1065 ms |
103040 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
