#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;
#define f first
#define s second
const int N=5e5+1;
int n, k;
vector<int> adj[N];
bool mark[N];
int dp[N], d[N];
vector<int> ans;
void dfs(int x, int par){
dp[x]=-1;
if(!d[x]) mark[x]=1;
for(int k:adj[x]){
if(k==par) continue;
dfs(k, x);
if(mark[k]) mark[x]=1;
dp[x]=max(dp[x], dp[k]-1);
}
if(mark[x] && dp[x]==d[x]) mark[x]=0;
if(mark[x] && d[par]!=d[x]+1){
ans.push_back(x);
dp[x]=d[x];
mark[x]=0;
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for(int i=0; i<n-1; i++){
int u,v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=1; i<=n; i++){
d[i]=-1;
}
queue<int> q;
while(k--){
int sheep;
cin >> sheep;
d[sheep]=0;
q.push(sheep);
}
for(; q.size(); q.pop()){
int x=q.front();
// cout << "d[" << x << "] " << d[x] << "\n";
for(int k:adj[x]){
if(d[k]==-1) d[k]=d[x]+1, q.push(k);
}
}
dfs(1, 0);
cout << ans.size() << "\n";
for(int x:ans) cout << x << " ";
}
// does it ever get lonely thinking you could live without me?
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
183 ms |
77400 KB |
Output is correct |
| 2 |
Correct |
209 ms |
77864 KB |
Output is correct |
| 3 |
Correct |
202 ms |
77768 KB |
Output is correct |
| 4 |
Correct |
274 ms |
83508 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
12268 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12332 KB |
Output is correct |
| 3 |
Correct |
453 ms |
39176 KB |
Output is correct |
| 4 |
Correct |
436 ms |
41416 KB |
Output is correct |
| 5 |
Correct |
581 ms |
38756 KB |
Output is correct |
| 6 |
Correct |
545 ms |
42284 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
12160 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12128 KB |
Output is correct |
| 3 |
Correct |
8 ms |
12132 KB |
Output is correct |
| 4 |
Correct |
8 ms |
12116 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12184 KB |
Output is correct |
| 6 |
Correct |
8 ms |
12128 KB |
Output is correct |
| 7 |
Correct |
8 ms |
12088 KB |
Output is correct |
| 8 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 9 |
Correct |
7 ms |
12076 KB |
Output is correct |
| 10 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 11 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 12 |
Correct |
7 ms |
12116 KB |
Output is correct |
| 13 |
Correct |
8 ms |
12080 KB |
Output is correct |
| 14 |
Correct |
8 ms |
12244 KB |
Output is correct |
| 15 |
Correct |
10 ms |
12116 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
520 ms |
39960 KB |
Output is correct |
| 2 |
Correct |
480 ms |
39696 KB |
Output is correct |
| 3 |
Correct |
474 ms |
42296 KB |
Output is correct |
| 4 |
Correct |
578 ms |
38764 KB |
Output is correct |
| 5 |
Correct |
384 ms |
37000 KB |
Output is correct |
| 6 |
Correct |
469 ms |
47260 KB |
Output is correct |
| 7 |
Correct |
462 ms |
45260 KB |
Output is correct |
| 8 |
Correct |
511 ms |
44884 KB |
Output is correct |
| 9 |
Correct |
615 ms |
38860 KB |
Output is correct |
| 10 |
Correct |
627 ms |
38820 KB |
Output is correct |
| 11 |
Correct |
450 ms |
40776 KB |
Output is correct |
| 12 |
Correct |
366 ms |
43652 KB |
Output is correct |
| 13 |
Correct |
422 ms |
45412 KB |
Output is correct |
| 14 |
Correct |
369 ms |
42344 KB |
Output is correct |
| 15 |
Correct |
79 ms |
16576 KB |
Output is correct |
| 16 |
Correct |
492 ms |
36808 KB |
Output is correct |
| 17 |
Correct |
329 ms |
37580 KB |
Output is correct |
| 18 |
Correct |
428 ms |
33972 KB |
Output is correct |
| 19 |
Correct |
528 ms |
45360 KB |
Output is correct |
| 20 |
Correct |
513 ms |
50252 KB |
Output is correct |
| 21 |
Correct |
498 ms |
38932 KB |
Output is correct |
| 22 |
Correct |
476 ms |
39856 KB |
Output is correct |
