#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX_N = 100005;
vector<int> tree[MAX_N];
int N, Q;
// HLD variables
int parent[MAX_N], depth[MAX_N], heavy[MAX_N], head[MAX_N], pos[MAX_N];
int curr_pos = 0;
// Segment Tree variables
struct Node {
int cats, dogs;
} segTree[4 * MAX_N];
int cats_in_node[MAX_N], dogs_in_node[MAX_N]; // Counts at nodes
int total_cats = 0, total_dogs = 0;
int danger_level = 0; // Total number of candidate edges
// Read input efficiently
void fast_io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
// DFS to compute sizes and heavy child
int dfs(int u, int p) {
int size = 1;
int max_subtree = 0;
parent[u] = p;
for (int v : tree[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
int subtree_size = dfs(v, u);
size += subtree_size;
if (subtree_size > max_subtree) {
max_subtree = subtree_size;
heavy[u] = v;
}
}
}
return size;
}
// Decompose the tree
void decompose(int u, int h) {
head[u] = h;
pos[u] = curr_pos++;
if (heavy[u] != -1) {
decompose(heavy[u], h);
}
for (int v : tree[u]) {
if (v != parent[u] && v != heavy[u]) {
decompose(v, v);
}
}
}
// Build the segment tree
void build_segTree(int node, int l, int r) {
segTree[node] = {0, 0};
if (l == r) {
return;
}
int mid = (l + r) / 2;
build_segTree(2 * node, l, mid);
build_segTree(2 * node + 1, mid + 1, r);
}
// Update the segment tree
void update_segTree(int node, int l, int r, int idx, int cat_diff, int dog_diff) {
if (l == r) {
segTree[node].cats += cat_diff;
segTree[node].dogs += dog_diff;
return;
}
int mid = (l + r) / 2;
if (idx <= mid) {
update_segTree(2 * node, l, mid, idx, cat_diff, dog_diff);
} else {
update_segTree(2 * node + 1, mid + 1, r, idx, cat_diff, dog_diff);
}
segTree[node].cats = segTree[2 * node].cats + segTree[2 * node + 1].cats;
segTree[node].dogs = segTree[2 * node].dogs + segTree[2 * node + 1].dogs;
}
// Query counts in a path
Node query_segTree(int node, int l, int r, int ql, int qr) {
if (qr < l || ql > r) return {0, 0};
if (ql <= l && r <= qr) {
return segTree[node];
}
int mid = (l + r) / 2;
Node left = query_segTree(2 * node, l, mid, ql, qr);
Node right = query_segTree(2 * node + 1, mid + 1, r, ql, qr);
return {left.cats + right.cats, left.dogs + right.dogs};
}
// Update counts along the path
void update_counts(int u, int cat_diff, int dog_diff) {
while (u != -1) {
update_segTree(1, 0, N - 1, pos[u], cat_diff, dog_diff);
u = parent[head[u]];
}
}
// Check and update candidate edges
void update_danger_level(int u, int cat_diff, int dog_diff) {
int prev_cats = cats_in_node[u];
int prev_dogs = dogs_in_node[u];
cats_in_node[u] += cat_diff;
dogs_in_node[u] += dog_diff;
bool prev_zero = (prev_cats == 0 && prev_dogs == 0);
bool curr_zero = (cats_in_node[u] == 0 && dogs_in_node[u] == 0);
if (prev_zero != curr_zero && parent[u] != -1) {
// Edge between u and parent[u] may change status
int u_cats = cats_in_node[u];
int u_dogs = dogs_in_node[u];
int p_cats = cats_in_node[parent[u]];
int p_dogs = cats_in_node[parent[u]];
Node total = query_segTree(1, 0, N - 1, 0, N - 1);
int cats_in_subtree = cats_in_node[u];
int dogs_in_subtree = dogs_in_node[u];
int cats_out_subtree = total_cats - cats_in_subtree;
int dogs_out_subtree = total_dogs - dogs_in_subtree;
bool was_candidate = false;
bool now_candidate = false;
// Previous status
if ((prev_cats > 0 && prev_dogs == 0 && dogs_out_subtree > 0) ||
(prev_dogs > 0 && prev_cats == 0 && cats_out_subtree > 0)) {
was_candidate = true;
}
// Current status
if ((cats_in_node[u] > 0 && dogs_in_node[u] == 0 && (total_dogs - dogs_in_node[u]) > 0) ||
(dogs_in_node[u] > 0 && cats_in_node[u] == 0 && (total_cats - cats_in_node[u]) > 0)) {
now_candidate = true;
}
if (was_candidate && !now_candidate) {
danger_level--;
} else if (!was_candidate && now_candidate) {
danger_level++;
}
}
}
// Initialize function
void initialize(int n, int A[], int B[]) {
N = n;
memset(heavy, -1, sizeof(heavy));
memset(cats_in_node, 0, sizeof(cats_in_node));
memset(dogs_in_node, 0, sizeof(dogs_in_node));
for (int i = 0; i < N - 1; ++i) {
int u = A[i];
int v = B[i];
tree[u].push_back(v);
tree[v].push_back(u);
}
parent[0] = -1;
depth[0] = 0;
dfs(0, -1);
decompose(0, 0);
build_segTree(1, 0, N - 1);
}
// Cat function
int cat(int v) {
total_cats++;
update_counts(v, 1, 0);
int u = v;
while (u != -1) {
update_danger_level(u, 1, 0);
u = parent[u];
}
return danger_level;
}
// Dog function
int dog(int v) {
total_dogs++;
update_counts(v, 0, 1);
int u = v;
while (u != -1) {
update_danger_level(u, 0, 1);
u = parent[u];
}
return danger_level;
}
// Neighbor function
int neighbor(int v) {
if (cats_in_node[v] > 0) {
total_cats--;
update_counts(v, -1, 0);
int u = v;
while (u != -1) {
update_danger_level(u, -1, 0);
u = parent[u];
}
} else if (dogs_in_node[v] > 0) {
total_dogs--;
update_counts(v, 0, -1);
int u = v;
while (u != -1) {
update_danger_level(u, 0, -1);
u = parent[u];
}
}
return danger_level;
}
// Main function
int main() {
fast_io();
int n;
cin >> n;
int A[MAX_N], B[MAX_N];
for (int i = 0; i < n - 1; ++i) {
cin >> A[i] >> B[i];
A[i]--; B[i]--;
}
initialize(n, A, B);
int Q;
cin >> Q;
for (int i = 0; i < Q; ++i) {
int T, v;
cin >> T >> v;
v--;
int res;
if (T == 1) {
res = cat(v);
} else if (T == 2) {
res = dog(v);
} else {
res = neighbor(v);
}
cout << res << endl;
}
return 0;
}
Compilation message
catdog.cpp: In function 'void update_danger_level(int, int, int)':
catdog.cpp:125:13: warning: unused variable 'u_cats' [-Wunused-variable]
125 | int u_cats = cats_in_node[u];
| ^~~~~~
catdog.cpp:126:13: warning: unused variable 'u_dogs' [-Wunused-variable]
126 | int u_dogs = dogs_in_node[u];
| ^~~~~~
catdog.cpp:127:13: warning: unused variable 'p_cats' [-Wunused-variable]
127 | int p_cats = cats_in_node[parent[u]];
| ^~~~~~
catdog.cpp:128:13: warning: unused variable 'p_dogs' [-Wunused-variable]
128 | int p_dogs = cats_in_node[parent[u]];
| ^~~~~~
catdog.cpp:130:14: warning: variable 'total' set but not used [-Wunused-but-set-variable]
130 | Node total = query_segTree(1, 0, N - 1, 0, N - 1);
| ^~~~~
/usr/bin/ld: /tmp/ccSomzCi.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccuHm4ui.o:catdog.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccSomzCi.o: in function `main':
grader.cpp:(.text.startup+0x1e2): undefined reference to `initialize(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
