样例 WA 求调。
查看原帖
样例 WA 求调。
1296826
lcfollower楼主2024/8/5 16:54

rt。。。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rint register int
#define PII pair <int, int>
const int N = 5e5 + 10 ,M = N;
inline void fre(){
  freopen("pastiri.in" ,"r" ,stdin);
  freopen("pastiri.out" ,"w" ,stdout);
} int n ,k ,fa[N] ,dep[N] ,dis[N]; bool vis[N];
priority_queue < PII , vector < PII > ,greater < PII > > q;
struct Edge{int to ,nxt;}edge[M << 1ll]; int cnt ,head[N] ,sheep[N];
bool cov[N]; vector <int> st;
inline void add(int u ,int v){edge[++cnt] = {v ,head[u]} ,head[u] = cnt;}
inline void dfs_init(int u ,int fath){
  fa[u] = fath ,dep[u] = dep[fath] + 1;
  for(int i = head[u] ; i ; i = edge[i].nxt) {int v = edge[i].to ; if(v == fath) continue; dfs_init(v ,u);}
} inline void dij(){
  memset(dis, 0x3f ,sizeof dis);
  for(rint i = 1 ; i <= k ; i ++){int x;scanf("%lld" ,&x);dis[x] = 0 ,q.push({x ,0});sheep[i] = x;}
  while(!q.empty()){
    int u = q.top().first;
    q.pop();
    if(vis[u]) continue;
    else vis[u] = 1;
    for(int i = head[u] ; i ; i = edge[i].nxt){
      int v = edge[i].to;
      if(dis[v] > dis[u] + 1){dis[v] = dis[u] + 1 , q.push({v ,dis[v]});}
    }
  }
} inline void cover(int u ,int sum){
  cov[u] = 1;
  if(!sum) return;
  for(int i = head[u] ; i ; i = edge[i].nxt){
  	int v = edge[i].to;
  	if(cov[v] || dis[v] != sum - 1) continue;
  	cover(v ,sum - 1);
  }
}inline void solve(){
  memset(fa ,-1 ,sizeof fa); 
  scanf("%lld %lld", &n , &k);
  for(rint i = 1;i < n; i ++){int u ,v;scanf("%lld %lld", &u ,&v);add(u ,v) ,add(v ,u);}
  dfs_init(1 ,0);
  dij();
  sort(sheep + 1 ,sheep + 1 + k ,[](int x ,int y){return dep[x] > dep[y];});
  for(rint i = 1;i <= n;i ++){
  	if(cov[sheep[i]]) continue;
    int u = sheep[i];
    while((~fa[u]) && dis[fa[u]] == dis[u] + 1) u = fa[u];
    st.push_back(u);
    cout << dep[sheep[i]] - dep[u] << endl;
	cover(u ,dep[sheep[i]] - dep[u]);
  }
  printf("%lld\n" ,st.size());
  for(int i : st) printf("%lld " ,i);
} signed main(){
  int Tcases = 1;
  while(Tcases --) solve();
  return 0;
} 
2024/8/5 16:54
加载中...