Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <map>
- #include <set>
- #include <array>
- #include <stack>
- #include <queue>
- #include <random>
- #include <numeric>
- #include <functional>
- #include <chrono>
- #include <utility>
- #include <iomanip>
- #include <assert.h>
- using namespace std;
- void dbg_out() { cerr << endl; }
- template<typename Head, typename... Tail>
- void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
- #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
- #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
- #define rng_seed(x) mt19937 rng(x)
- #define all(x) (x).begin(), (x).end()
- #define sz(x) (int) (x).size()
- // #define int long long
- const int MXN = 1e5 + 5, INF = 1e9 + 5;
- int N, Q, node;
- vector<pair<char, int>> queries;
- vector<int> g[MXN];
- vector<pair<int, int>> par[MXN];
- int subtree[MXN];
- bool vis[MXN];
- struct two_set {
- pair<int, int> x = {-INF, -1}, y = {-INF, -1};
- void insert(int dist, int id) {
- pair<int, int> z = make_pair(dist, id);
- if (x.second == id) x = max(y, z);
- else y = max(y, z);
- if (x.first < y.first) swap(x, y);
- }
- int query(int id) {
- return (x.second == id ? y.first : x.first);
- }
- };
- two_set best[MXN];
- void calc_subtree(int u, int p) {
- subtree[u] = 1;
- for (const auto &v : g[u]) {
- if (v == p) continue;
- calc_subtree(v, u);
- subtree[u] += subtree[v];
- }
- }
- int find_centroid(int u, int p, int vertices) {
- if (p != -1) {
- subtree[p] -= subtree[u];
- subtree[u] += subtree[p];
- }
- for (const auto &v : g[u]) {
- if (v == p || vis[v]) continue;
- if (subtree[v] * 2 > vertices)
- return find_centroid(v, u, vertices);
- }
- return u;
- }
- void dfs(int u, int p, int dist, int centroid) {
- par[u].emplace_back(centroid, dist);
- for (const auto &v : g[u]) {
- if (v == p || vis[v]) continue;
- dfs(v, u, dist + 1, centroid);
- }
- }
- void build_tree(int u) {
- int centroid = find_centroid(u, -1, subtree[u]);
- vis[centroid] = true;
- for (const auto &v : g[centroid]) {
- if (vis[v]) continue;
- dfs(v, centroid, 1, centroid);
- }
- for (const auto &v : g[centroid]) {
- if (vis[v]) continue;
- build_tree(v);
- }
- }
- void add_node(int v) {
- best[v].insert(0, v);
- int child = v;
- for (const auto &[centroid, dist] : par[v]) {
- best[centroid].insert(dist, child);
- child = centroid;
- }
- }
- int query(int v) {
- int ans = best[v].x.first, child = v;
- for (const auto &[centroid, dist] : par[v]) {
- if (centroid < node)
- ans = max(ans, dist + best[centroid].query(child));
- child = centroid;
- }
- return ans;
- }
- void solve() {
- cin >> Q;
- for (int i = 0; i < Q; i++) {
- char type;
- int x;
- cin >> type >> x;
- x--;
- queries.emplace_back(type, x);
- if (type == 'B') {
- if (x < 0) {
- N++;
- continue;
- }
- g[N].push_back(x);
- g[x].push_back(N);
- N++;
- }
- }
- for (int i = 0; i < N; i++) {
- if (vis[i]) continue;
- calc_subtree(i, -1);
- build_tree(i);
- }
- for (int i = 0; i < N; i++)
- reverse(all(par[i]));
- vector<bool> built(N, false);
- for (const auto &[type, v] : queries) {
- if (type == 'B') {
- if (v < 0) {
- node++;
- continue;
- }
- if (!built[v]) {
- add_node(v);
- built[v] = true;
- }
- add_node(node);
- built[node++] = true;
- } else {
- cout << (built[v] ? max(0, query(v)) : 0) << "\n";
- }
- }
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- #ifndef local
- freopen("newbarn.in", "r", stdin);
- freopen("newbarn.out", "w", stdout);
- #endif
- int TC = 1;
- // cin >> TC;
- while (TC--) solve();
- }
Add Comment
Please, Sign In to add comment