結果

問題 No.3442 Good Vertex Connectivity
コンテスト
ユーザー areik
提出日時 2026-02-06 23:09:03
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 1,107 ms / 3,000 ms
コード長 5,032 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,756 ms
コンパイル使用メモリ 237,344 KB
実行使用メモリ 88,184 KB
最終ジャッジ日時 2026-02-06 23:09:56
合計ジャッジ時間 51,353 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/fenwicktree.hpp>
#include <atcoder/segtree.hpp>
using namespace std;

using i32 = int;
using i64 = long long;
using f64 = double;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
  _main();
}

vector<i64> et;
i64 li[200000], ri[200000];
i64 dep[200000], siz[200000], par[200000];
vector<i64> g[200000];
void dfs(i64 v) {
  li[v] = ri[v] = et.size();
  et.push_back(v);
  siz[v] = 1;
  for (i64 nv : g[v]) {
    if (nv == par[v]) continue;
    dep[nv] = dep[v] + 1;
    par[nv] = v;
    dfs(nv);
    siz[v] += siz[nv];
    ri[v] = et.size();
    et.push_back(v);
  }
}
p2 opn(p2 a, p2 b) {return min(a, b);}
p2 en() {return {1e18, 1e18};}
void _main() {
  i64 n;
  cin >> n;
  for (i64 i = 0; i < n - 1; i++) {
    i64 a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  par[0] = -1, dep[0] = 0;
  dfs(0);
  atcoder::segtree<p2, opn, en> seglca(et.size());
  atcoder::fenwick_tree<i64> bit(et.size());
  for (i64 i = 0; i < et.size(); i++) {
    seglca.set(i, {dep[et[i]], et[i]});
  }
  vector<i64> c(n);
  set<i64> st;
  auto add = [&](i64 i) {
    auto it = st.lower_bound(li[i]);
    if (it != st.begin() && it != st.end()) {
      i64 l = *prev(it), r = *it;
      i64 lca = seglca.prod(l, r + 1).second;
      bit.add(r, -(dep[et[r]] - dep[lca]));
    }
    if (it != st.end()) {
      i64 r = *it;
      i64 lca = seglca.prod(li[i], r + 1).second;
      bit.add(r, dep[et[r]] - dep[lca]);
    }
    if (it != st.begin()) {
      i64 l = *prev(it);
      i64 lca = seglca.prod(l, li[i] + 1).second;
      bit.add(li[i], dep[i] - dep[lca]);
    }
    c[i] ^= 1;
    st.insert(li[i]);
  };
  auto sub = [&](i64 i) {
    c[i] ^= 1;
    st.erase(li[i]);
    auto it = st.lower_bound(li[i]);
    if (it != st.begin()) {
      i64 l = *prev(it);
      i64 lca = seglca.prod(l, li[i] + 1).second;
      bit.add(li[i], -(dep[i] - dep[lca]));
    }
    if (it != st.end()) {
      i64 r = *it;
      i64 lca = seglca.prod(li[i], r + 1).second;
      bit.add(r, -(dep[et[r]] - dep[lca]));
    }
    if (it != st.begin() && it != st.end()) {
      i64 l = *prev(it), r = *it;
      i64 lca = seglca.prod(l, r + 1).second;
      bit.add(r, dep[et[r]] - dep[lca]);
    }
  };
  vector<vector<i64>> dl(20, vector<i64>(n, -1));
  for (i64 i = 0; i < n; i++) dl[0][i] = par[i];
  for (i64 i = 1; i < dl.size(); i++) {
    for (i64 j = 0; j < n; j++) {
      if (dl[i - 1][j] == -1) continue;
      dl[i][j] = dl[i - 1][dl[i - 1][j]];
    }
  }
  for (i64 i = 0; i < n; i++) {
    i64 x;
    cin >> x;
    if (x == 1) add(i);
  }
  i64 q;
  cin >> q;
  for (;q--;) {
    i64 op;
    cin >> op;
    if (op == 1) {
      i64 i;
      cin >> i;
      i--;
      if (c[i] == 0) {
        add(i);
      } else {
        sub(i);
      }
      continue;
    }
    i64 x, y;
    cin >> x >> y;
    x--, y--;
    if (st.empty()) {
      cout << "0\n";
      continue;
    }
    i64 llccaa = seglca.prod(min(li[x], li[y]), max(li[x], li[y]) + 1).second;
    if (x == y) x = -1, y = 0, llccaa = -1;
    if (llccaa != y) {
      i64 i = y;
      auto it1 = st.lower_bound(li[i]);
      auto it2 = st.lower_bound(ri[i] + 1);
      if (it1 == it2) {
        cout << "0\n";
        continue;
      }
      if (it1 == st.begin()) {
        i64 l = *it1, r = *prev(it2);
        i64 lca = seglca.prod(l, r + 1).second;
        i64 ans = bit.sum(l, r + 1);
        ans += dep[et[l]] - dep[lca];
        cout << ans + 1 << "\n";
        continue;
      }
      i64 ans = bit.sum(li[i], ri[i] + 1);
      i64 l = *it1, r = *prev(it2);
      i64 ll = *prev(it1);
      i64 lca1 = seglca.prod(l, r + 1).second;
      i64 lca2 = seglca.prod(ll, l + 1).second;
      ans -= dep[lca1] - dep[lca2];
      cout << ans + 1 << "\n";
      continue;
    }
    for (i64 i = dl.size() - 1; i >= 0; i--) {
      if (dl[i][x] == -1 || dep[dl[i][x]] <= dep[y]) continue;
      x = dl[i][x];
    }
    assert(dep[x] == dep[y] + 1);
    i64 i = x;
    auto it1 = st.lower_bound(li[i]);
    auto it2 = st.lower_bound(ri[i] + 1);
    i64 ans = 0;
    i64 L = 1e18, R = -1e18;
    if (it1 != st.begin()) {
      i64 l = *st.begin(), r = *prev(it1);
      ans += bit.sum(l, r + 1);
      L = min(L, l);
      R = max(R, r);
    }
    if (it2 != st.end()) {
      i64 l = *it2, r = *prev(st.end());
      ans += bit.sum(l, r + 1);
      L = min(L, l);
      R = max(R, r);
      if (it2 != st.begin()) {
        i64 ll = *prev(it2);
        i64 lca = seglca.prod(ll, l + 1).second;
        ans -= dep[et[l]] - dep[lca];
      }
    }
    if (it1 != st.begin() && it2 != st.end()) {
      i64 l = *prev(it1), r = *it2;
      i64 lca = seglca.prod(l, r + 1).second;
      ans += dep[et[r]] - dep[lca];
    }
    if (L == 1e18) {
      cout << "0\n";
      continue;
    }
    i64 lca = seglca.prod(L, R + 1).second;
    ans += dep[et[L]] - dep[lca];
    cout << ans + 1 << "\n";
  }
}
0