#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,k,tot;
int v[1000005],nxt[1000005],h[500005],a[500005],dep[500005],d[500005],f[21][500005],sz[500005],cp[21][500005],ds[21][500005],mx[500005];
bool hv[500005],del[500005];
void addedge(int x,int y){
v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
v[++tot]=x; nxt[tot]=h[y]; h[y]=tot;
}
void dfs(int x,int fa){
dep[x]=dep[fa]+1;
f[0][x]=fa;
for(int i=1;i<21;i++) f[i][x]=f[i-1][f[i-1][x]];
for(int p=h[x];p;p=nxt[p]){
if(v[p]==fa) continue;
dfs(v[p],x);
}
}
void bfs(){
for(int i=1;i<=n;i++) d[i]=-1;
queue<int> q;
for(int i=1;i<=k;i++){
d[a[i]]=0;
q.push(a[i]);
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int p=h[x];p;p=nxt[p]){
if(d[v[p]]==-1){
d[v[p]]=d[x]+1;
q.push(v[p]);
}
}
}
}
void dfssz(int x,int fa){
sz[x]=1;
for(int p=h[x];p;p=nxt[p]){
if(del[v[p]]||v[p]==fa) continue;
dfssz(v[p],x);
sz[x]+=sz[v[p]];
}
}
int findcen(int x,int fa,int n){
for(int p=h[x];p;p=nxt[p]){
if(del[v[p]]||v[p]==fa||sz[v[p]]*2<=n) continue;
return findcen(v[p],x,n);
}
return x;
}
void go(int x,int fa,int s,int dd){
cp[dd][x]=s;
ds[dd][x]=ds[dd][fa]+1;
for(int p=h[x];p;p=nxt[p]){
if(del[v[p]]||v[p]==fa) continue;
go(v[p],x,s,dd);
}
}
void build(int x,int dd){
dfssz(x,x);
x=findcen(x,x,sz[x]);
del[x]=true;
go(x,x,x,dd);
for(int p=h[x];p;p=nxt[p]){
if(del[v[p]]) continue;
build(v[p],dd+1);
}
}
bool query(int x){
for(int i=0;i<21;i++){
if(mx[cp[x][i]]>=ds[x][i]) return true;
if(cp[x][i]==x) break;
}
return false;
}
void update(int x){
for(int i=0;i<21;i++){
chkmax(mx[cp[x][i]],d[x]+1-(ds[x][i]-1));
if(cp[x][i]==x) break;
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--) if(dep[f[i][x]]>=dep[y]) x=f[i][x];
for(int i=10;i>=0;i--) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
return x==y?x:f[0][x];
}
int dist(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
int main(){
n=readint(); k=readint();
for(int i=1;i<n;i++) addedge(readint(),readint());
for(int i=1;i<=k;i++) a[i]=readint();
dfs(1,1);
bfs();
build(1,0);
sort(a+1,a+k+1,[&](int i,int j){return dep[i]>dep[j];});
for(int i=1;i<=k;i++){
bool ok=false;
for(int j=1;j<=n;j++){
if(hv[j]&&dist(a[i],j)==d[j]) ok=true;
}
if(ok) continue;
int ver=a[i];
while(f[0][ver]!=ver&&dep[a[i]]-dep[f[0][ver]]==d[f[0][ver]]) ver=f[0][ver];
hv[ver]=true;
}
vector<int> ans;
for(int i=1;i<=n;i++) if(hv[i]) ans.pb(i);
printf("%d\n",ans.size());
for(int i:ans) printf("%d ",i);
return 0;
}
Compilation message
pastiri.cpp: In function 'int main()':
pastiri.cpp:145:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
145 | printf("%d\n",ans.size());
| ~^ ~~~~~~~~~~
| | |
| int std::vector<int>::size_type {aka long unsigned int}
| %ld
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
288 ms |
167252 KB |
Output is correct |
| 2 |
Correct |
684 ms |
167760 KB |
Output is correct |
| 3 |
Correct |
724 ms |
167888 KB |
Output is correct |
| 4 |
Execution timed out |
1064 ms |
168112 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
72532 KB |
Output is correct |
| 2 |
Correct |
11 ms |
72668 KB |
Output is correct |
| 3 |
Correct |
940 ms |
118392 KB |
Output is correct |
| 4 |
Correct |
821 ms |
112396 KB |
Output is correct |
| 5 |
Execution timed out |
1089 ms |
139980 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
70232 KB |
Output is correct |
| 2 |
Correct |
12 ms |
70236 KB |
Output is correct |
| 3 |
Correct |
38 ms |
70236 KB |
Output is correct |
| 4 |
Correct |
43 ms |
59996 KB |
Output is correct |
| 5 |
Correct |
33 ms |
72284 KB |
Output is correct |
| 6 |
Correct |
38 ms |
70384 KB |
Output is correct |
| 7 |
Correct |
11 ms |
72284 KB |
Output is correct |
| 8 |
Correct |
10 ms |
72280 KB |
Output is correct |
| 9 |
Correct |
9 ms |
64196 KB |
Output is correct |
| 10 |
Correct |
9 ms |
62044 KB |
Output is correct |
| 11 |
Correct |
15 ms |
59864 KB |
Output is correct |
| 12 |
Correct |
11 ms |
59996 KB |
Output is correct |
| 13 |
Correct |
54 ms |
57976 KB |
Output is correct |
| 14 |
Correct |
21 ms |
72544 KB |
Output is correct |
| 15 |
Correct |
27 ms |
72392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
139312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
