#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 1e5+5;
const int INF = 1e9;
in col[3] = {{0, INF}, {INF, 0}, {0, 0}};
in contrib(in a)
{
return {min(a[0], a[1]+1), min(a[0]+1, a[1])};
}
struct cdata
{
int v[2][2];
void init(in ab)
{
v[0][0] = ab[0];
v[1][1] = ab[1];
v[0][1] = v[1][0] = INF;
return;
}
cdata operator+(const cdata &m)
{
cdata x;
if((v[0][0] < 0))
return m;
if((m.v[0][0] < 0))
{
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
x.v[i][j] = v[i][j];
return x;
}
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < 2; j++)
{
x.v[i][j] = INF;
for(int jp = 0; jp < 2; jp++)
{
for(int ip = 0; ip < 2; ip++)
x.v[i][j] = min(x.v[i][j], v[i][jp] + m.v[ip][j] + (ip^jp));
}
}
}
return x;
}
};
cdata cope;
struct seg_tree
{
vector<cdata> tree;
void init(int n)
{
tree.resize(4*n+13);
for(auto &s: tree)
s.init(col[2]);
return;
}
void upd(in val, int p, int id, int l, int r)
{
if(l == r)
{
tree[id].init(val);
return;
}
int m = (l+r)/2;
if(p <= m)
upd(val, p, 2*id, l, m);
else
upd(val, p, 2*id+1, m+1, r);
tree[id] = tree[2*id] + tree[2*id+1];
return;
}
cdata query(int ql, int qr, int id, int l, int r)
{
if(qr < l || r < ql)
return cope;
if((ql <= l) && (r <= qr))
return tree[id];
int m = (l+r)/2;
return query(ql, qr, 2*id, l, m) + query(ql, qr, 2*id+1, m+1, r);
}
};
int NN;// = n.
seg_tree work;
vector<int> temp;//serves no real purpose honestly, for convenience.
vector<int> adj[MX];
vector<int> head(MX);
vector<int> lv(MX);
vector<int> pa(MX);
vector<int> sub(MX);
void dfs1(int u, int p)
{
sub[u] = 1;
pa[u] = p;
temp.clear();
for(int v: adj[u])
{
if(v == p)
continue;
temp.pb(v);
}
swap(adj[u], temp);
in bst = {-1, -1};
for(int s = 0; s < adj[u].size(); s++)
{
dfs1(adj[u][s], u);
sub[u]+=sub[adj[u][s]];
bst = max(bst, {sub[adj[u][s]], s});
}
if(bst[1] > 0)
swap(adj[u][0], adj[u][bst[1]]);
return;
}
int tin[MX];
int TIMER;
void dfs2(int u)
{
tin[u] = ++TIMER;
if(adj[u].empty())
{
lv[u] = u;
return;
}
head[adj[u][0]] = head[u];
dfs2(adj[u][0]);
lv[u] = lv[adj[u][0]];
for(int v: adj[u])
{
if(v == adj[u][0]) continue;
head[v] = v; dfs2(v);
}
return;
}
vector<in> dp(MX);//current total contribution. it is really only important for the Heads.
vector<in> light(MX);//current contribution from ONLY light children. we maintain this for everyone.
vector<in> cur(MX);//current stuff.
void initialize(int n, vector<int> a, vector<int> b)
{
NN = n;
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
cope.v[i][j] = -1;
for(int i = 0; i < n-1; i++)
{
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
}
for(int i = 1; i <= n; i++)
{
cur[i] = {0, 0};
light[i] = {0, 0};
dp[i] = {0, 0};
}
dfs1(1, 0);
head[1] = 1;
TIMER = 0;
dfs2(1);
work.init(n);
return;
}
int upd_light(int u, in LT)
{
int x = head[u];
light[u] = LT;
work.upd(LT, tin[u], 1, 1, NN);
cdata C = work.query(tin[x], tin[lv[u]], 1, 1, NN);
in ndp = {min(C.v[0][0], C.v[0][1]), min(C.v[1][0], C.v[1][1])};
in noww = contrib(ndp);
in earli = contrib(dp[x]);
dp[x] = ndp;//correct the dp value
int z = pa[x];
if(z == 0)
return min(dp[x][0], dp[x][1]);
in LTp;//we need to compute LTp
LTp[0] = noww[0] - earli[0] + light[z][0];
LTp[1] = noww[1] - earli[1] + light[z][1];
return upd_light(z, LTp);
}
int upd(int u, in Lt)
{
in dlt = {Lt[0]-cur[u][0], Lt[1]-cur[u][1]};
cur[u] = Lt;
in Ltp = {light[u][0] + dlt[0], light[u][1] + dlt[1]};
return upd_light(u, Ltp);
}
int cat(int v)
{
return upd(v, {0, INF});
}
int dog(int v)
{
return upd(v, {INF, 0});
}
int neighbor(int v)
{
return upd(v, {0, 0});
}
