#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ll long long
int parent[100001], depth[100001], heavy[100001], head[100001], pos[100001], revpos[100001], tail[100001];
vector<vector<int>> segment; //0 is dog dog, 1 is dog cat, 2 is cat dog, 3 is cat cat
vector<vector<int>> graph;
int curpos = 0, bottom = 0;
vector<int> merge(vector<int> a, vector<int> b) {
if (a[0] == -1) return b;
if (b[0] == -1) return a;
//cout << "MERGE" << endl;
//for (int i: a) cout << i << ' '; cout << endl;
//for (int i: b) cout << i << ' '; cout << endl;
vector<int> bruh(4);
bruh[0] = min(a[0] + b[0], min(a[0] + b[2] + 1, min(a[1] + b[0] + 1, a[1] + b[2])));
bruh[1] = min(a[0] + b[1], min(a[0] + b[3] + 1, min(a[1] + b[1] + 1, a[1] + b[3])));
bruh[2] = min(a[2] + b[0], min(a[2] + b[2] + 1, min(a[3] + b[0] + 1, a[3] + b[2])));
bruh[3] = min(a[2] + b[1], min(a[2] + b[3] + 1, min(a[3] + b[1] + 1, a[3] + b[3])));
for (int i=0;i<4;i++) bruh[i] = min(1010000000, bruh[i]);
//for (int i: bruh) cout << i << ' '; cout << endl;
return bruh;
}
void change(int pos, vector<int> val) {
pos += 131072;
segment[pos] = val;
while (pos > 1) {
pos /= 2;
segment[pos] = merge(segment[2 * pos], segment[2 * pos + 1]);
}
}
vector<int> segquery(int a, int b) {
if (a > b) swap(a, b);
a += 131072; b += 131072;
vector<int> left(4, -1), right(4, -1);
while (a <= b) {
if (a % 2 == 1) left = merge(left, segment[a++]);
if (b % 2 == 0) right = merge(segment[b--], right);
a /= 2; b /= 2;
}
return merge(left, right);
}
int dfs(int v) {
int size = 1;
int max_c_size = 0;
for (int c : graph[v]) {
if (c != parent[v]) {
parent[c] = v; depth[c] = depth[v] + 1;
int c_size = dfs(c);
size += c_size;
if (c_size > max_c_size) max_c_size = c_size, heavy[v] = c;
}
}
return size;
}
void decompose(int v, int h) {
head[v] = h, pos[v] = curpos, revpos[curpos++] = v;
if (heavy[v] != -1) decompose(heavy[v], h);
for (int i : graph[v]) {
if (i != parent[v] && i != heavy[v]) decompose(i, i);
}
}
void process(int a, vector<int> newval) {
vector<int> oldgroup = segquery(pos[tail[a]], pos[head[a]]);
change(pos[a], newval);
vector<int> newgroup = segquery(pos[tail[a]], pos[head[a]]);
if (head[a] == 0) return;
//cout << a << ' ' << tail[a] << ' ' << head[a] << ' ' << "ORIGINALVAL" << endl;
//for (int i: segment[pos[a] + 131072]) cout << i << ' '; cout << endl;
//cout << "OLDGROUP" << a << endl;
//for (int i: oldgroup) cout << i << ' '; cout << endl;
//cout << "NEWGROUP" << a << endl;
//for (int i: newgroup) cout << i << ' '; cout << endl;
//cout << "==================" << endl;
int olddog = min(oldgroup[0], min(oldgroup[1], min(oldgroup[2] + 1, oldgroup[3] + 1)));
int oldcat = min(oldgroup[0] + 1, min(oldgroup[1] + 1, min(oldgroup[2], oldgroup[3])));
int newdog = min(newgroup[0], min(newgroup[1], min(newgroup[2] + 1, newgroup[3] + 1)));
int newcat = min(newgroup[0] + 1, min(newgroup[1] + 1, min(newgroup[2], newgroup[3])));
vector<int> changevec = segment[pos[parent[head[a]]] + 131072];
changevec[0] += newdog - olddog, changevec[3] += newcat - oldcat;
process(parent[head[a]], changevec);
}
void initialize(int n, vector<int> arra, vector<int> arrb) {
for (int i=0;i<n;i++) heavy[i] = -1;
graph = vector<vector<int>> (n);
for (int i=0;i<n-1;i++) {
arra[i]--; arrb[i]--;
graph[arra[i]].pb(arrb[i]);
graph[arrb[i]].pb(arra[i]);
}
parent[0] = 0, depth[0] = 1;
dfs(0); decompose(0, 0);
//for (int i=0;i<n;i++) cout << pos[i] << ' '; cout << endl;
//for (int i=0;i<n;i++) cout << revpos[i] << ' '; cout << endl;
int curtail = revpos[n - 1];
tail[revpos[n - 1]] = curtail;
for (int i=n-2;i>-1;i--) {
if (head[revpos[i]] != head[revpos[i + 1]]) curtail = revpos[i];
tail[revpos[i]] = curtail;
}
segment = vector<vector<int>> (262144, vector<int>(4, 0));
for (int i=131072;i<262144;i++) segment[i][1] = 1000000000, segment[i][2] = 1000000000;
for (int i=0;i<n;i++) if (head[i] == 0 && depth[i] > depth[bottom]) bottom = i;
bottom = pos[bottom];
}
int cat(int v) {
v -= 1;
vector<int> lmao = segment[pos[v] + 131072]; lmao[0] += 1000000000; process(v, lmao);
//for (int i: segment[pos[2] + 131072]) cout << i << ' '; cout << endl;
//for (int i: segment[pos[1] + 131072]) cout << i << ' '; cout << endl;
//for (int i: segment[pos[0] + 131072]) cout << i << ' '; cout << endl; cout << endl;
lmao = segquery(0, bottom);
return *min_element(lmao.begin(), lmao.end());
}
int dog(int v) {
v -= 1;
vector<int> lmao = segment[pos[v] + 131072]; lmao[3] += 1000000000; process(v, lmao);
//for (int i: segment[pos[2] + 131072]) cout << i << ' '; cout << endl;
//for (int i: segment[pos[1] + 131072]) cout << i << ' '; cout << endl;
//for (int i: segment[pos[0] + 131072]) cout << i << ' '; cout << endl; cout << endl;
lmao = segquery(0, bottom);
return *min_element(lmao.begin(), lmao.end());
}
int neighbor(int v) {
v -= 1;
vector<int> lmao = segment[pos[v] + 131072];
if (lmao[0] >= 1000000000) lmao[0] -= 1000000000;
else lmao[3] -= 1000000000;
process(v, lmao);
//for (int i: segment[pos[2] + 131072]) cout << i << ' '; cout << endl;
//for (int i: segment[pos[1] + 131072]) cout << i << ' '; cout << endl;
//for (int i: segment[pos[0] + 131072]) cout << i << ' '; cout << endl; cout << endl;
lmao = segquery(0, bottom);
return *min_element(lmao.begin(), lmao.end());
}
