結果
| 問題 | No.3442 Good Vertex Connectivity |
| コンテスト | |
| ユーザー |
 iastm
|
| 提出日時 | 2026-02-08 15:16:42 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,187 ms / 3,000 ms |
| コード長 | 12,346 bytes |
| 記録 | |
| コンパイル時間 | 4,308 ms |
| コンパイル使用メモリ | 207,436 KB |
| 実行使用メモリ | 96,648 KB |
| 最終ジャッジ日時 | 2026-02-08 15:18:05 |
| 合計ジャッジ時間 | 72,273 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 69 |
ソースコード
#include <iostream>
#include <vector>
#include <atcoder/segtree>
// #include <kotone/lca>
// https://github.com/amiast/cpp-utility
#ifndef KOTONE_LCA_HPP
#define KOTONE_LCA_HPP 1
#include <vector>
#include <algorithm>
#include <cassert>
// #include <kotone/dsu>
// https://github.com/amiast/cpp-utility
#ifndef KOTONE_DSU_HPP
#define KOTONE_DSU_HPP 1
#include <vector>
#include <cassert>
#include <algorithm>
namespace kotone {
// A basic data structure that monitors connectivity in a graph.
// Optionally monitors the potential differences between nodes.
// Reference: AtCoder Library
template <typename T = int> struct dsu {
protected:
int _num_nodes;
bool _defines_pd = true;
std::vector<int> _parent_or_size;
std::vector<T> _p;
T _potential(int v) {
leader(v);
return _p[v];
}
public:
dsu() : _num_nodes(0) {}
// Creates a graph with the specified `num_nodes` and no edges.
dsu(int num_nodes) : _num_nodes(num_nodes), _parent_or_size(num_nodes, -1), _p(num_nodes) {
assert(num_nodes >= 0);
assert(num_nodes <= 100000000);
}
// Returns the leader of the connected component containing `v`.
int leader(int v) {
assert(v >= 0);
assert(v < _num_nodes);
if (_parent_or_size[v] < 0) return v;
int l = leader(_parent_or_size[v]);
_p[v] = _p[v] + _p[_parent_or_size[v]];
return _parent_or_size[v] = l;
}
// Returns whether `u` and `v` belong to the same connected component.
bool connected(int u, int v) {
return leader(u) == leader(v);
}
// Returns the potential difference from `u` to `v`.
// Requires `u` and `v` to be connected.
// Requires all previous `merge()` calls to define potential differences.
T potential_diff(int u, int v) {
assert(connected(u, v));
assert(_defines_pd);
return _potential(v) - _potential(u);
};
// Adds an edge between `u` and `v`,
// then returns the leader of the merged component.
virtual int merge(int u, int v) {
_defines_pd = false;
return merge(u, v, T{});
}
// Adds an edge between `u` and `v`,
// then returns the leader of the merged component.
// If `u` and `v` are not formerly connected,
// defines the potential difference from `u` to `v` as `pd`.
virtual int merge(int u, int v, T pd) {
if (connected(u, v)) return leader(u);
pd = pd + _potential(u) - _potential(v);
u = leader(u);
v = leader(v);
if (_parent_or_size[u] > _parent_or_size[v]) {
std::swap(u, v);
pd = -pd;
}
_parent_or_size[u] += _parent_or_size[v];
_parent_or_size[v] = u;
_p[v] = pd;
return u;
}
// Returns the size of the connected component containing `v`.
int size(int v) {
return -_parent_or_size[leader(v)];
}
// Returns a vector of connected components as vectors of node indices.
// The order of components is undefined.
// Node indices in each group's vector appear in ascending order.
std::vector<std::vector<int>> components() {
std::vector<std::vector<int>> temp(_num_nodes), result;
for (int i = 0; i < _num_nodes; i++) temp[leader(i)].emplace_back(i);
for (int i = 0; i < _num_nodes; i++) {
if (temp[i].size()) {
result.push_back(std::move(temp[i]));
}
}
return result;
}
};
// An extended DSU with internal mapping between connected components and a semigroup.
// Optionally monitors the potential differences between nodes.
template <typename S, S (*op)(S, S), typename T = int> struct extended_dsu : dsu<T> {
protected:
std::vector<S> _map;
public:
extended_dsu() : dsu<T>() {}
// Creates a graph with the specified `num_nodes` and no edges.
// Each connected component is mapped to a value-initialized instance of `S`.
extended_dsu(int num_nodes) : dsu<T>(num_nodes), _map(num_nodes) {}
// Creates a graph with the specified `num_nodes` and no edges.
// Each connected component is mapped to a copy of `init_x`.
extended_dsu(int num_nodes, S init_x) : dsu<T>(num_nodes), _map(num_nodes, init_x) {}
// Creates a graph with no edges.
// For all `v`, maps connected component containing `v` to `vec[v]`.
extended_dsu(const std::vector<S> &vec) : dsu<T>(vec.size()), _map(vec) {}
// Adds an edge between `u` and `v`,
// then returns the leader of the merged component.
// Also merges their images under the mapping.
int merge(int u, int v) override {
this->_defines_pd = false;
return merge(u, v, T{});
}
// Adds an edge between `u` and `v`,
// then returns the leader of the merged component.
// Also merges their images under the mapping.
// If `u` and `v` are not formerly connected,
// defines the potential difference from `u` to `v` as `pd`.
int merge(int u, int v, T pd) override {
if (this->connected(u, v)) return this->leader(u);
S result = op(_map[this->leader(u)], _map[this->leader(v)]);
_map[dsu<T>::merge(u, v, pd)] = std::move(result);
return this->leader(u);
}
// Returns a copy of the image mapped from the connected component containing `v`.
S get(int v) {
return _map[this->leader(v)];
}
// Reassigns `x` as the image mapped from the connected component containing `v`,
// then returns the leader of the modified component.
int set(int v, S x) {
v = this->leader(v);
_map[v] = std::move(x);
return v;
}
};
} // namespace kotone
#endif // KOTONE_DSU_HPP
namespace kotone {
// A data structure that manages the lowest common ancestors (LCA) of nodes in a tree (forest).
struct lca_tree {
private:
int _num_nodes = 0;
std::vector<std::vector<int>> _tree, _sparse_table;
std::vector<int> _depth, _euler, _level, _first, _log, _is_root;
dsu<int> _dsu;
bool _requires_build = false;
bool _is_rooted = true;
void _euler_tour(int u, int p, int d) {
_depth[u] = d;
_first[u] = _euler.size();
_euler.push_back(u);
_level.push_back(d);
for (int v : _tree[u]) {
if (v == p) continue;
_euler_tour(v, u, d + 1);
_euler.push_back(u);
_level.push_back(d);
}
}
void _build() {
if (!_requires_build) return;
_requires_build = false;
_euler.clear();
_level.clear();
for (int i = 0; i < _num_nodes; i++) {
if (
(_is_rooted && _is_root[i])
|| (!_is_rooted && i == _dsu.leader(i))
) _euler_tour(i, -1, 0);
}
int M = _euler.size();
_log.resize(M + 1);
for (int i = 2; i <= M; i++) _log[i] = _log[i / 2] + 1;
int K = _log[M] + 1;
_sparse_table.assign(K, std::vector<int>(M));
for (int i = 0; i < M; i++) _sparse_table[0][i] = i;
for (int k = 1; k < K; k++) {
for (int i = 0; i + (1 << k) <= M; i++) {
int x = _sparse_table[k - 1][i];
int y = _sparse_table[k - 1][i + (1 << (k - 1))];
_sparse_table[k][i] = _level[x] < _level[y] ? x : y;
}
}
}
public:
lca_tree() {}
// Constructs a tree for the specified number of nodes.
lca_tree(int num_nodes) : _num_nodes(num_nodes), _dsu(num_nodes) {
assert(0 <= num_nodes && num_nodes <= 100000000);
_tree.resize(num_nodes);
_depth.resize(num_nodes);
_first.resize(num_nodes);
_is_root.resize(num_nodes, 1);
}
// Returns the number of nodes in the tree.
int size() const noexcept {
return _num_nodes;
}
// Adds an edge between the specified parent and child nodes.
// If `child` already has an assigned parent, the tree becomes undirected.
// - This alters the behavior of `get_lca`.
//
// Requires `parent` and `child` to be formerly disconnected.
// Requires `0 <= parent < num_nodes`.
// Requires `0 <= child < num_nodes`.
void add_edge(int parent, int child) {
assert(0 <= parent && parent < _num_nodes);
assert(0 <= child && child < _num_nodes);
assert(!_dsu.connected(parent, child));
if (!_is_root[child]) _is_rooted = false;
_tree[parent].push_back(child);
_tree[child].push_back(parent);
_dsu.merge(parent, child);
_is_root[child] = false;
_requires_build = true;
}
// Prompts the tree to build the LCA table immediately.
void build() {
_build();
}
// Returns the lowest common ancestor of nodes `u` and `v`.
// If `u` and `v` are disconnected, returns `-1`.
// If the tree is undirected due to the effect of `add_edge`,
// the LCA is assigned to be an arbitrary node in the tree (or the connected component in a forest).
// Requires `0 <= u < num_nodes`.
// Requires `0 <= v < num_nodes`.
int get_lca(int u, int v) {
assert(0 <= u && u < _num_nodes);
assert(0 <= v && v < _num_nodes);
if (_requires_build) _build();
if (u == v) return u;
if (!_dsu.connected(u, v)) return -1;
int L = _first[u], R = _first[v];
if (L > R) std::swap(L, R);
int k = _log[R - L + 1];
int x = _sparse_table[k][L];
int y = _sparse_table[k][R - (1 << k) + 1];
return _level[x] < _level[y] ? _euler[x] : _euler[y];
}
// Returns the distance between nodes `u` and `v`.
// If `u` and `v` are disconnected, returns `-1`.
// Requires `0 <= u < num_nodes`.
// Requires `0 <= v < num_nodes`.
int get_distance(int u, int v) {
int w = get_lca(u, v);
if (w == -1) return -1;
return _depth[u] + _depth[v] - _depth[w] * 2;
}
};
} // namespace kotone
#endif // KOTONE_LCA_HPP
kotone::lca_tree lca_tree;
struct S {
int l = -1, r = -1;
int64_t dist = 0;
};
S op(S a, S b) {
if (a.l == -1) return b;
if (b.l == -1) return a;
return {a.l, b.r, a.dist + b.dist + lca_tree.get_distance(a.r, b.l)};
}
S e() { return {}; }
int main() {
int N;
std::cin >> N;
lca_tree = kotone::lca_tree(N);
std::vector<std::vector<int>> tree(N);
for (int i = 1; i < N; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
tree[u].push_back(v);
tree[v].push_back(u);
}
int time = 0;
std::vector<int> order(N), order_of(N), out(N);
std::vector<std::vector<int>> jump(18, std::vector<int>(N));
auto eval_order = [&](auto &eval_order, int u, int p) -> void {
order[u] = time;
order_of[time++] = u;
for (int v : tree[u]) {
if (v == p) continue;
lca_tree.add_edge(u, v);
jump[0][v] = u;
eval_order(eval_order, v, u);
}
out[u] = time;
};
eval_order(eval_order, 0, 0);
for (int k = 0; k < 17; k++) {
for (int i = 0; i < N; i++) {
jump[k + 1][i] = jump[k][jump[k][i]];
}
}
std::vector<S> vec(N);
for (int i = 0; i < N; i++) {
int c;
std::cin >> c;
if (c == 0) continue;
vec[order[i]] = {i, i, 0};
}
atcoder::segtree<S, op, e> seg(vec);
int Q;
std::cin >> Q;
while (Q--) {
int t;
std::cin >> t;
if (t == 1) {
int v;
std::cin >> v;
v--;
if (seg.get(order[v]).l == -1) seg.set(order[v], {v, v, 0});
else seg.set(order[v], {});
continue;
}
int x, y;
std::cin >> x >> y;
x--, y--;
S prod;
if (x == y) prod = seg.all_prod();
else if (!(order[y] <= order[x] && order[x] < out[y])) prod = seg.prod(order[y], out[y]);
else {
int d = lca_tree.get_distance(y, x) - 1;
for (int k = 0; k < 18; k++) {
if (d >> k & 1) x = jump[k][x];
}
prod = op(seg.prod(0, order[x]), seg.prod(out[x], N));
}
if (prod.l == -1) std::cout << 0 << std::endl;
else std::cout << (prod.dist + lca_tree.get_distance(prod.l, prod.r)) / 2 + 1 << std::endl;
}
}