#include "catdog.h"
#include <iostream>
#include <stack>
#include <map>
#include <vector>
#include <string>
#include <cassert>
#include <unordered_map>
#include <queue>
#include <cstdint>
#include <cstring>
#include <limits.h>
#include <cmath>
#include <set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int, int>
#define ppii pair<int, pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F(n) for (int i = 0; i < n; i++)
#define lb lower_bound
#define ub upper_bound
#define fastio \
ios::sync_with_stdio(false); \
cin.tie(NULL);
#pragma GCC optimize("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod = 1e9 + 7, mxn = 1e5 + 5, inf = 1e6, minf = -1e6, lg = 30;
int x, n;
struct mat
{
int M[2][2];
mat()
{
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
M[i][j] = 0;
}
mat operator*(mat o)
{
if (o.M[0][0] == minf)
return (*this);
if (M[0][0] == minf)
return o;
mat c;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
{
c.M[i][j] = inf;
for (int k = 0; k < 2; k++)
{
c.M[i][j] = min(c.M[i][j], M[i][k] + o.M[k][j]);
}
}
return c;
}
void operator+=(mat &o)
{
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
M[i][j] += o.M[i][j];
}
void operator-=(mat &o)
{
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
M[i][j] -= o.M[i][j];
}
};
mat dummy;
void print(mat x)
{
cout << "print\n";
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
cout << x.M[i][j] << " ";
cout << '\n';
}
}
struct seg
{
mat v[4 * mxn + 10];
void update(int qpos, mat x, int pos = 1, int l = 1, int r = n)
{
if (l > qpos || r < qpos)
return;
if (l == r)
{
return void(v[pos] = x);
}
int mid = l + (r - l) / 2;
update(qpos, x, pos << 1, l, mid);
update(qpos, x, pos << 1 | 1, mid + 1, r);
v[pos] = (v[pos << 1] * v[pos << 1 | 1]);
}
void updateA(int qpos, mat x, int pos = 1, int l = 1, int r = n)
{
if (l > qpos || r < qpos)
return;
if (l == r)
return void(v[pos] += x);
int mid = l + (r - l) / 2;
updateA(qpos, x, pos << 1, l, mid);
updateA(qpos, x, pos << 1 | 1, mid + 1, r);
v[pos] = (v[pos << 1] * v[pos << 1 | 1]);
}
mat qry(int ql, int qr, int pos = 1, int l = 1, int r = n)
{
if (l > qr || r < ql)
return dummy;
if (ql <= l && r <= qr)
return v[pos];
int mid = l + (r - l) / 2;
return (qry(ql, qr, pos << 1, l, mid) * qry(ql, qr, pos << 1 | 1, mid + 1, r));
}
} t;
int hvy[mxn + 10], hvyp[mxn + 10], sz[mxn + 10];
int tin[mxn + 10], tout[mxn + 10], T = 0, tail[mxn + 10], up[mxn + 10];
int dp[mxn + 10][2];
mat last[mxn + 10];
vector<int> adj[mxn + 10];
mat mul;
void getsz(int cur, int p)
{
sz[cur] = 1;
for (auto i : adj[cur])
if (i != p)
getsz(i, cur), sz[cur] += sz[i];
}
void hld(int cur, int p, int hp)
{
tin[cur] = ++T;
hvyp[cur] = hp;
tail[hvyp[cur]] = max(tail[hvyp[cur]], tin[cur]);
for (auto i : adj[cur])
if (i != p && sz[hvy[cur]] < sz[i])
hvy[cur] = i;
if (hvy[cur])
hld(hvy[cur], cur, hp);
for (auto i : adj[cur])
if (i != p && hvy[cur] != i)
hld(i, cur, i);
tout[cur] = T;
}
void calup(int cur)
{
cur = hvyp[cur];
mat aft = t.qry(tin[cur], tail[cur]) * mul;
int x = aft.M[0][0], y = aft.M[1][1];
mat delta;
delta.M[0][0] = min(x, y + 1) - dp[cur][0];
delta.M[0][1] = min(x, y + 1) - dp[cur][0];
delta.M[1][1] = min(x + 1, y) - dp[cur][1];
delta.M[1][1] = min(x + 1, y) - dp[cur][1];
dp[cur][0] = min(x, y + 1);
dp[cur][1] = min(x + 1, y);
if (up[cur])
{
t.updateA(tin[up[cur]], delta);
}
}
void dfs(int cur, int p)
{
mat c;
c.M[0][1] = c.M[1][0] = 1;
t.update(tin[cur], c);
last[cur] = c;
for (auto i : adj[cur])
{
if (i == p)
continue;
up[i] = cur;
dfs(i, cur);
}
if (cur == hvyp[cur])
{
calup(cur);
}
}
void initialize(int32_t N, std::vector<int32_t> A, std::vector<int32_t> B)
{
dummy.M[0][0] = minf;
n = N;
for (int i = 0; i < n - 1; i++)
{
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
getsz(1, -1);
hld(1, -1, 1);
dfs(1, -1);
}
int32_t cat(int32_t cur)
{
mat x;
x.M[0][1] = x.M[1][1] = inf;
x.M[1][0] = 1;
x -= last[cur];
last[cur] = x;
t.updateA(tin[cur], x);
while (cur)
{
calup(hvyp[cur]);
cur = up[hvyp[cur]];
}
calup(hvyp[cur]);
return min(dp[1][0], dp[1][1]);
}
int32_t dog(int32_t cur)
{
mat x;
x.M[0][0] = x.M[1][0] = inf;
x.M[0][1] = 1;
x -= last[cur];
last[cur] = x;
t.updateA(tin[cur], x);
while (cur)
{
calup(hvyp[cur]);
cur = up[hvyp[cur]];
}
return min(dp[1][0], dp[1][1]);
}
int32_t neighbor(int32_t cur)
{
mat x;
x.M[1][0] = x.M[1][0] = 1;
x -= last[cur];
last[cur] = x;
t.updateA(tin[cur], x);
while (cur)
{
calup(hvyp[cur]);
cur = up[hvyp[cur]];
}
return min(dp[1][0], dp[1][1]);
}
/*
5
1 2
2 3
2 4
4 5
2
1 3
2 5
5
1 2
2 3
3 4
4 5
2
1 4
2 5
5
1 2
2 3
2 4
1 5
5
1 3
1 5
1 2
2 1
3 2
*/
