結果

問題 No.3189 Semifinal Stage
ユーザー 蜜蜂
提出日時 2025-06-07 04:36:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 603 ms / 4,000 ms
コード長 2,528 bytes
コンパイル時間 1,584 ms
コンパイル使用メモリ 134,128 KB
実行使用メモリ 37,776 KB
最終ジャッジ日時 2025-06-19 19:13:57
合計ジャッジ時間 14,228 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
using namespace std;

#include <atcoder/segtree>
using namespace atcoder;

int main(){
  int n;
  cin >> n;

  vector<vector<int>> g(n);
  for(int i = 0; i < n - 1; i++){
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  vector<int> par(n, -1);
  vector<int> sub(n, 0);
  vector<int> dep(n, 0);

  auto dfs = [&](auto& dfs, int now) -> void {
    for(int nxt: g[now]){
      if(nxt == par[now]) continue;
      par[nxt] = now;
      dep[nxt] = dep[now] + 1;
      dfs(dfs, nxt);
      sub[now] += sub[nxt];
    }
    sub[now]++;
    return;
  };

  dfs(dfs, 0);
  
  vector<vector<int>> paths = {{}};

  auto dfs2 = [&](auto& dfs2, int now, int key) -> void {
    paths[key].emplace_back(now);
    int arg = -1;
    for(int nxt: g[now]){
      if(nxt == par[now]) continue;
      if(sub[nxt] > sub[arg]) arg = nxt;
    }
    if(arg != -1) dfs2(dfs2, arg, key);
    for(int nxt: g[now]){
      if(nxt == par[now] || nxt == arg) continue;
      paths.emplace_back();
      dfs2(dfs2, nxt, paths.size() - 1);
    }
  };

  dfs2(dfs2, 0, 0);

  vector<int> inv_idx(n), which_path(n), idx_in_path(n);
  int c = 0, d = 0;
  for(vector<int> path: paths){
    int e = 0;
    for(int vertex: path){
      inv_idx[vertex] = c;
      which_path[vertex] = d;
      idx_in_path[vertex] = e;
      c++;
      e++;
    }
    d++;
  }

  segtree<int, [](int a, int b){return min(a, b);}, [](){return 1e9;}> seg1(n), seg2(n);
  vector<set<pair<int, int>>> sets(n);
  vector<int> col(n, 0);
  for(int i = 0; i < n; i++) sets[i].insert({1e9, -1});

  int q;
  cin >> q;
  while(q--){
    int t, v;
    cin >> t >> v;
    v--;
    if(t == 1){
      int pos = v;
      pair<int, int> p = {dep[v], v};
      while(true){
        if(col[v] == 0) sets[pos].insert(p);
        else sets[pos].erase(p);
        int d = (*sets[pos].begin()).first;
        seg1.set(inv_idx[pos], d);
        seg2.set(inv_idx[pos], d - 2 * dep[pos]);
        pos = par[paths[which_path[pos]][0]];
        if(pos == -1) break;
      }
      col[v] ^= 1;
    }
    else{
      int ans = 1e9;
      int pos = v;
      while(true){
        ans = min(ans, seg1.prod(inv_idx[pos], inv_idx[paths[which_path[pos]].back()] + 1) + dep[v] - 2 * dep[pos]);
        ans = min(ans, seg2.prod(inv_idx[pos] - idx_in_path[pos], inv_idx[pos] + 1) + dep[v]);
        pos = par[paths[which_path[pos]][0]];
        if(pos == -1) break;
      }
      cout << ans << endl;
    }
  }
}
0