#include "catdog.h" #include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int maxN = 1e6 + 5; const int inf = 1e9; int n; vector<int> adj[maxN]; struct Tnode { int cost[2][2]; Tnode() { cost[0][0] = 0; cost[1][0] = inf; cost[0][1] = inf; cost[1][1] = 0; } void init() { cost[0][0] = 0; cost[1][0] = 0; cost[0][1] = 0; cost[1][1] = 0; } Tnode operator + (const Tnode& other) const { if (other.cost[0][0] == -1) return *this; if (cost[0][0] == -1) return other; Tnode res; res.cost[0][0] = inf; res.cost[1][1] = inf; for (int a = 0; a < 2; ++a) for (int b = 0; b < 2; ++b) for (int c = 0; c < 2; ++c) for (int d = 0; d < 2; ++d) { res.cost[a][b] = min(cost[a][c] + other.cost[d][b] + (c != d), res.cost[a][b]); } return res; } void add(Tnode x) { int cat = min(x.cost[0][0], x.cost[0][1]); int dog = min(x.cost[1][0], x.cost[1][1]); cat = min(cat, dog + 1); dog = min(dog, cat + 1); cost[0][0] += cat; cost[0][1] += dog; cost[1][0] += cat; cost[1][1] += dog; } void del(Tnode x) { int cat = min(x.cost[0][0], x.cost[0][1]); int dog = min(x.cost[1][0], x.cost[1][1]); cat = min(cat, dog + 1); dog = min(dog, cat + 1); cost[0][0] -= cat; cost[0][1] -= dog; cost[1][0] -= cat; cost[1][1] -= dog; } int ans() { return min({cost[0][0], cost[1][1], cost[0][1], cost[1][0]}); } } st[2 * maxN], f[maxN]; int hepa[maxN], idpa[maxN], id[maxN], sz[maxN], bc[maxN], dep[maxN], p[maxN]; int in[maxN], out[maxN]; int cnt, cntpa; void predfs(int u, int par) { p[u] = par; sz[u] = 1; bc[u] = -1; for (int v : adj[u]) { if (v == par) continue; dep[v] = dep[u] + 1; predfs(v, u); sz[u] += sz[v]; if (bc[u] == -1 || sz[bc[u]] < sz[v]) bc[u] = v; } } void hld(int u) { idpa[u] = cntpa; id[u] = ++cnt; if (hepa[cntpa] == 0) { hepa[cntpa] = u; in[cntpa] = cnt; } out[cntpa] = cnt; if (bc[u] > 0) hld(bc[u]); for (int v : adj[u]) { if (v == p[u] || v == bc[u]) continue; ++cntpa; hld(v); } } void update(int id, int l, int r, int i, Tnode val) { if (i < l || i > r) return; if (l == r) { st[id] = val; return; } int mid = (l + r) / 2; update(id << 1, l, mid, i, val); update(id << 1 | 1, mid + 1, r, i, val); st[id] = st[id << 1] + st[id << 1 | 1]; } Tnode get(int id, int l, int r, int u, int v) { if (l > v || r < u) { Tnode tmp = Tnode(); tmp.cost[0][0] = -1; return tmp; } if (u <= l && r <= v) return st[id]; int mid = (l + r) / 2; return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v); } Tnode modify(int type, Tnode x) { if (type == 0) x.cost[1][1] = x.cost[1][0] = x.cost[0][1] = inf; if (type == 1) x.cost[0][0] = x.cost[1][0] = x.cost[0][1] = inf; if (type == 2) x.cost[0][1] = x.cost[1][0] = inf; return x; } void query(int u, int type) { int u0 = u; while (idpa[u] != 0) { f[p[hepa[idpa[u]]]].del(get(1, 1, n, in[idpa[u]], out[idpa[u]])); update(1, 1, n, id[u], modify(type, f[u])); f[p[hepa[idpa[u]]]].add(get(1, 1, n, in[idpa[u]], out[idpa[u]])); u = p[hepa[idpa[u]]]; } // cerr << f[2].cost[0][0] << " " << in[idpa[u]] << " " << get(1, 1, n, in[idpa[u0]], out[idpa[u0]]).cost[0][0] << "sd1\n"; // cerr << f[2].cost[0][1] << " " << out[idpa[u0]] << " " << get(1, 1, n, in[idpa[u0]], out[idpa[u0]]).cost[0][1] << "sd2\n"; // cerr << f[2].cost[1][0] << " " << idpa[u0] << " " << get(1, 1, n, in[idpa[u0]], out[idpa[u0]]).cost[1][0] << "sd3\n"; // cerr << f[2].cost[1][1] << " " << id[u0] << " " << get(1, 1, n, in[idpa[u0]], out[idpa[u0]]).cost[1][1] << "sd4\n"; } void initialize(int N, vector<int> A, vector<int> B) { // Tnode tmp0, tmp; // tmp0.cost[0][0] = 0; // tmp0.cost[0][1] = inf; // tmp0.cost[1][0] = inf; // tmp0.cost[1][1] = inf; // tmp.cost[0][0] = inf; // tmp.cost[0][1] = inf; // tmp.cost[1][0] = inf; // tmp.cost[1][1] = 0; // cerr << (tmp + tmp0).cost[0][0] << "A\n"; // cerr << (tmp + tmp0).cost[0][1] << "B\n"; // cerr << (tmp + tmp0).cost[1][0] << "C\n"; // cerr << (tmp + tmp0).cost[1][1] << "D\n"; n = N; for (int i = 0; i < n - 1; ++i) { adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); } predfs(1, 0); cnt = 0; cntpa = 1; hld(1); for (int i = 1; i <= n; ++i) f[i].init(); } int cat(int v) { query(v, 0); return get(1, 1, n, in[1], out[1]).ans(); } int dog(int v) { query(v, 1); return get(1, 1, n, in[1], out[1]).ans(); } int neighbor(int v) { query(v, 2); return get(1, 1, n, in[1], out[1]).ans(); }