#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int maxn = 100010;
const int inf = 1000000000;
int subsize[maxn];
int bigch[maxn];
int myspot[maxn];
int mycol[maxn]; //store the current color of this node
vector<int> preorder; //this is the special preorder thing
vector<int> adj[maxn];
int par[maxn];
int chainhead[maxn]; //pretty sure this is all that matters
//don't need tail??
int chainend[maxn];
int ccost[maxn][2]; //cost of being colored 1 or 2
int pardiff[maxn][2];
struct mat {
int v[2][2];
};
const bool debug = false;
mat seg[maxn*4];
void printmat(mat & thing) {
cout << thing.v[0][0] << ", " << thing.v[0][1] << ", " << thing.v[1][0] <<
", " << thing.v[1][1] << endl;
}
mat merge(mat& a, mat& b) {
//no reason to not pass by reference
mat res;
res.v[0][0] = res.v[0][1] = res.v[1][0] = res.v[1][1] = inf;
for (int i = 0; i <= 1; i++) {
for (int j = 0; j <= 1; j++) {
res.v[i][j] = min(res.v[i][j],
a.v[i][0] + b.v[0][j]);
res.v[i][j] = min(res.v[i][j],
a.v[i][0] + 1 + b.v[1][j]);
res.v[i][j] = min(res.v[i][j],
a.v[i][1] + 1 + b.v[0][j]);
res.v[i][j] = min(res.v[i][j],
a.v[i][1] + b.v[1][j]);
}
}
// if (debug) {
// cout << " merge of ";
// printmat(a);
// cout << " and ";
// printmat(b);
// cout << " produces ";
// printmat(res);
// }
return res;
}
void predfs(int u, int p = -1) {
par[u] = p;
if (debug) cout << u << " has parent " << p << endl;
subsize[u] = 1;
for (int v : adj[u]) {
if (v == p) continue;
predfs(v, u);
subsize[u] += subsize[v];
if (subsize[v] > subsize[bigch[u]]) {
bigch[u] = v;
}
}
}
void dfs(int u) {
preorder.push_back(u);
myspot[u] = preorder.size()-1;
if (par[u] != -1 && bigch[par[u]] == u) {
chainhead[u] = chainhead[par[u]];
}
else chainhead[u] = u;
if (debug) cout << "dfs: " << u << " has head " << chainhead[u] << endl;
chainend[chainhead[u]] = u; //now I am the smallest
if (bigch[u]) {
dfs(bigch[u]);
}
for (int v : adj[u]) {
if (v != bigch[u] && v != par[u]) {
dfs(v);
}
}
}
void buildtree(int ss = 1, int se = n, int si = 0) {
//pretty sure this is a useless method
if (ss == se) {
seg[si].v[0][0] = seg[si].v[0][1] = seg[si].v[1][0] = seg[si].v[1][1] = inf;
if (mycol[preorder[ss]] != 1) seg[si].v[1][1] = 0 + ccost[preorder[ss]][1];
if (mycol[preorder[ss]] != 2) seg[si].v[0][0] = 0 + ccost[preorder[ss]][0];
return;
}
int mid = (ss+se)/2;
buildtree(ss, mid, si*2+1);
buildtree(mid+1, se, si*2+2);
seg[si] = merge(seg[si*2+1], seg[si*2+2]);
}
void upd(int spot, int ss = 1, int se = n, int si = 0) {
if (ss == se) {
//update explicitly
seg[si].v[0][0] = seg[si].v[0][1] = seg[si].v[1][0] = seg[si].v[1][1] = inf;
if (mycol[preorder[ss]] != 1) seg[si].v[1][1] = 0 + ccost[preorder[ss]][1];
if (mycol[preorder[ss]] != 2) seg[si].v[0][0] = 0 + ccost[preorder[ss]][0];
if (debug) {
cout << "updating " << spot << endl;
cout << " "; printmat(seg[si]);
}
return;
}
int mid = (ss+se)/2;
if (spot <= mid) upd(spot, ss, mid, si*2+1);
else upd(spot, mid+1, se, si*2+2);
seg[si] = merge(seg[si*2+1], seg[si*2+2]);
}
mat zs; //zeroes
mat query(int qs, int qe, int ss = 1, int se = n, int si = 0) {
if (qs > qe || ss > se || qs > se || qe < ss) return zs;
if (qs <= ss && se <= qe) {
return seg[si];
}
int mid = (ss+se)/2;
if (qs > mid) {
return query(qs, qe, mid+1, se, si*2+2);
}
if (qe <= mid) {
return query(qs, qe, ss, mid, si*2+1);
}
mat lhs = query(qs, qe, ss, mid, si*2+1);
mat rhs = query(qs, qe, mid+1, se, si*2+2);
return merge(lhs, rhs);
}
int uph(int u) {
//update up the HLD structure
// if (debug) cout << "start of an HLD trek: ";
while (true) { //should return eventually
int nx = chainhead[u];
// cout << u << " goes to " << nx << endl;
upd(myspot[u]);
if (debug) {
cout << " " << u << " :: " << ccost[u][0] << " - " << ccost[u][1] << endl;
mat cccc = query(myspot[u], myspot[u]);
cout << " "; printmat(cccc) ;
}
mat cv = query(myspot[nx], myspot[chainend[nx]]);
int c0 = min(cv.v[0][0], cv.v[0][1]);
int c1 = min(cv.v[1][0], cv.v[1][1]);
// if (debug) cout << u << " ";
if (nx == 1) {
// cout << "THING THING: ";
// printmat(cv);
// if (debug) cout << 1 << endl;
if (debug) cout << c0 << " VVVVV " << c1 << endl;
// if (debug) cout << "CCOSTS: " << ccost[1][0] << " -- " << ccost[1][1] << endl;
return min(c0, c1);
}
// if (debug) cout << " at " << u << " with " << c0 << " and " << c1 << endl;
// if (debug) {
// cout << " ";
// printmat(cv);
// }
int op = par[nx];
ccost[op][0] += min(c0, c1 + 1) - min(pardiff[nx][0], pardiff[nx][1] + 1);
ccost[op][1] += min(c1, c0 + 1) - min(pardiff[nx][1], pardiff[nx][0] + 1);
pardiff[nx][0] = c0;
pardiff[nx][1] = c1;
u = op;
}
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for (int i = 0; i < N-1; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
par[1] = -1;
preorder.push_back(-1); //just buffer it so I can one-index
predfs(1);
dfs(1); //this is to get the preorder
buildtree(); //do not need this because the answer is
zs.v[0][1] = zs.v[1][0] = inf;
// cout << "DONE WITH INIT" << endl;
}
int cat(int v) {
if (debug) cout << "CAT at " << v << endl;
mycol[v] = 1;
return uph(v);
}
int dog(int v) {
if (debug) cout << "DOG at " << v << endl;
mycol[v] = 2;
if (debug) uph(v);
if (debug) {
for (int i = 1; i <= n; i++) {
cout << i << " ::: ";
mat cc = query(myspot[i], myspot[i]);
printmat(cc);
}
}
return uph(v);
}
int neighbor(int v) {
if (debug) cout << "EMPTY at " << v << endl;
mycol[v] = 0;
return uph(v);
}
//THIS IS DONE IN THE WEIRD IOI STYLE
//MUST BE DONE ONLINE
//let's do the HLD thing where ranges are consecutive in a single segment tree
