結果

問題 No.1718 Random Squirrel
ユーザー 👑 NachiaNachia
提出日時 2021-10-22 23:21:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,980 bytes
コンパイル時間 1,096 ms
コンパイル使用メモリ 96,392 KB
実行使用メモリ 29,420 KB
最終ジャッジ日時 2024-09-23 07:51:25
合計ジャッジ時間 4,643 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 WA -
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 WA -
testcase_10 AC 2 ms
6,944 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 88 ms
11,320 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 85 ms
11,712 KB
testcase_25 WA -
testcase_26 AC 45 ms
12,224 KB
testcase_27 AC 47 ms
11,736 KB
testcase_28 AC 46 ms
11,728 KB
testcase_29 AC 50 ms
17,836 KB
testcase_30 AC 98 ms
28,260 KB
testcase_31 AC 56 ms
24,988 KB
testcase_32 AC 50 ms
17,712 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(n); i++)

struct heavy_light_decomposition{
private:

  int N;
  vector<int> P;
  vector<int> PP;
  vector<int> PD;
  vector<int> D;
  vector<int> I;

  vector<int> rangeL;
  vector<int> rangeR;

public:

  heavy_light_decomposition(const vector<vector<int>>& E = {{}}){
    N = E.size();
    P.assign(N, -1);
    I = {0};
    I.reserve(N);
    for(int i=0; i<I.size(); i++){
      int p = I[i];
      for(int e : E[p]) if(P[p] != e){
        I.push_back(e);
        P[e] = p;
      }
    }
    vector<int> Z(N, 1);
    vector<int> nx(N, -1);
    PP.resize(N);
    for(int i=0; i<N; i++) PP[i] = i;
    for(int i=N-1; i>=1; i--){
      int p = I[i];
      Z[P[p]] += Z[p];
      if(nx[P[p]] == -1) nx[P[p]] = p;
      if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p;
    }

    for(int p : I) if(nx[p] != -1) PP[nx[p]] = p;

    PD.assign(N,N);
    PD[0] = 0;
    D.assign(N,0);
    for(int p : I) if(p != 0){
      PP[p] = PP[PP[p]];
      PD[p] = min(PD[PP[p]], PD[P[p]]+1);
      D[p] = D[P[p]]+1;
    }
    
    rangeL.assign(N,0);
    rangeR.assign(N,0);
    vector<int> dfs;
    dfs.push_back(0);
    while(dfs.size()){
      int p = dfs.back();
      rangeR[p] = rangeL[p] + Z[p];
      int ir = rangeR[p];
      dfs.pop_back();
      for(int e : E[p]) if(P[p] != e) if(e != nx[p]){
        rangeL[e] = (ir -= Z[e]);
        dfs.push_back(e);
      }
      if(nx[p] != -1){
        rangeL[nx[p]] = rangeL[p] + 1;
        dfs.push_back(nx[p]);
      }
    }

    I.resize(N);
    for(int i=0; i<N; i++) I[rangeL[i]] = i;
  }

  int depth(int p) const {
    return D[p];
  }

  int lca(int u, int v) const {
    if(PD[u] < PD[v]) swap(u, v);
    while(PD[u] > PD[v]) u = P[PP[u]];
    while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; }
    return (D[u] > D[v]) ? v : u;
  }

  int dist(int u, int v) const {
    return depth(u) + depth(v) - depth(lca(u,v)) * 2;
  }

  vector<pair<int,int>> path(int r, int c, bool include_root = true, bool reverse_path = false) const {
    vector<pair<int,int>> res;
    while(PD[r] < PD[c]){
      res.push_back({ rangeL[PP[c]], rangeL[c]+1 });
      c = P[PP[c]];
    }
    if(PP[r] != PP[c]) return {};
    if(D[r] > D[c]) return {};
    res.push_back({ rangeL[r], rangeL[c]+1 });
    if(!include_root){
      res.back().first++;
      if(res.back().first == res.back().second) res.pop_back();
    }
    if(!reverse_path) reverse(res.begin(),res.end());
    return move(res);
  }

  const vector<int>& idxs() const {
    return rangeL;
  }

  int meet(int x, int y, int z) const {
    return lca(x,y) ^ lca(y,z) ^ lca(x,z);
  }

  int jump(int from, int to, int d) const {
    int g = lca(from,to);
    int dist0 = D[from] - D[g] * 2 + D[to];
    if(dist0 > d) return -1;
    int p = from;
    if(D[from] - D[g] > d){ p = to; d = dist0 - d; }
    while(D[p] - D[PP[p]] > d){
      d -= D[p] - D[PP[p]] + 1;
      p = P[PP[p]];
    }
    return I[rangeL[p] - d];
  }
};



template<class T> using nega_queue = priority_queue<T,vector<T>,greater<T>>;


int main(){
  int N; cin >> N;
  int K; cin >> K;
  vector<vector<int>> E(N);
  rep(i,N-1){
    int u,v; cin >> u >> v; u--; v--;
    E[u].push_back(v);
    E[v].push_back(u);
  }

  vector<int> Xlist;
  vector<int> X(N, 0);
  rep(k,K){ int x; cin >> x; Xlist.push_back(x-1); X[x-1] = 1; }
  
  vector<vector<pair<int,int>>> Xpathedges;
  vector<vector<int>> Xpaths;

  auto dfs = [&](int p, int pre, auto dfs)->void{
    if(X[p]){
      Xpathedges.push_back({});
      Xpaths.push_back({p});
    }
    for(int e : E[p]) if(e != pre){
      Xpathedges.back().push_back({p,e});
      dfs(e, p ,dfs);
      Xpathedges.back().push_back({e,p});
    }
  };
  dfs(Xlist[0], -1, dfs);

  for(auto& path : Xpathedges){
    vector<pair<int,int>> buf;
    for(auto a : path){
      if(buf.size()) if(buf.back().first == a.second){ buf.pop_back(); continue; }
      buf.push_back(a);
    }
    path = move(buf);
  }
  
  rep(i,Xpathedges.size()){
    for(auto e : Xpathedges[i]) Xpaths[i].push_back(e.second);
  }

  //for(auto path : Xpaths){
  //  for(auto a : path) cout << a << " ";
  //  cout << endl;
  //}

  i64 ans_offset = 0;
  for(auto& path : Xpaths) ans_offset += path.size() - 1;

  nega_queue<pair<int,int>> G;
  vector<int> dist(N, 1001001001);
  for(auto& path : Xpaths) rep(i,path.size()) G.push({ -max<int>(i,path.size()-1-i), path[i] });
  while(G.size()){
    int d = G.top().first;
    int p = G.top().second;
    G.pop();
    if(dist[p] != 1001001001) continue;
    dist[p] = d;
    for(int e : E[p]) if(dist[e] == 1001001001) G.push({ d+1, e });
  }

  rep(i,N) cout << (ans_offset + dist[i]) << "\n";

  return 0;
}




struct ios_do_not_sync {
    ios_do_not_sync() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0