#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cerr<<#x << " : " << x << "\n";
using namespace std ;
const int maxn = 4e5 + 10 , mod = 1e9 + 7 , inf =1e17 ;
int n , c[maxn] , par[maxn] , d[maxn] ,cnt = 2 , s[maxn][2] , mark[maxn];
vector <int> G[maxn] ;
struct node{
int a[2][2] ;
};
node operator+(node a, node b){
node res ;
rep(i,0,1)rep(j,0,1)res.a[i][j] = inf ;
rep(i,0,1)
rep(j,0,1)
rep(k,0,1)
rep(z,0,1)
res.a[i][j] = min(res.a[i][j] , a.a[i][k] + b.a[z][j] + (k!=z)) ;
return res;
}
struct segtree{
int id ;
vector <int> az ;
vector <node> seg;
void UPD(int x ,int p ,int l , int r ){
int mid = (l+r)/2, pl=p<<1 , pr =p<<1|1 ;
if(x > r || x < l)return ;
if(l==r){
seg[p].a[0][1] = seg[p].a[1][0] = seg[p].a[0][0] = seg[p].a[1][1] = inf ;
if(mark[az[x]] == 0 || mark[az[x]] == 1)seg[p].a[0][0] = s[az[x]][0] ;
if(mark[az[x]] == 0 || mark[az[x]] == 2)seg[p].a[1][1] = s[az[x]][1] ;
return ;
}
UPD(x,pl,l,mid);
UPD(x,pr,mid+1,r);
seg[p] = seg[pl] + seg[pr] ;
}
void upd(int x){
UPD(x,1 ,0 ,sz(az)-1) ;
}
void bui(){
rep(i , 0 , 4*sz(az)+2){
node res ;
seg.pb(res) ;
}
rep(i , 0 , sz(az)-1){
upd(i);
}
}
};
segtree h[maxn] ;int sb[maxn] ;
void d1(int v, int p=0){
sb[v] = 1;
for(int u : G[v]){
if(u == p)continue ;
d1(u , v);
sb[v] += sb[u] ;
}
}
void d2(int v , int p =0){
vector <pii> vec ;
for(int u : G[v]){
if(u == p)continue ;
vec.pb({sb[u] , u}) ;
}
sort(all(vec)) ;
per(i , sz(vec)-1 , 0){
int u = vec[i].S ;
if(i == sz(vec)-1){
par[u] = par[v] ;
c[u]=c[v] ;
h[c[u]].az.pb(u) ;
d[u] = d[v] + 1 ;
d2(u , v);
}else{
par[u] = v ;
c[u] = cnt ;
h[cnt].az.pb(u) ;
cnt++;
d[u] =0 ;
d2(u , v) ;
}
}
if(sz(vec)==0){
h[c[v]].bui() ;
}
}
void ch(int v){
if(c[v]==1){
h[c[v]].upd(d[v]);
return ;
}
rep(i , 0 , 1)
s[par[v]][i]-=min(min(h[c[v]].seg[1].a[i][0],h[c[v]].seg[1].a[i][1]),min(h[c[v]].seg[1].a[!i][0],h[c[v]].seg[1].a[!i][1])+1) ;
h[c[v]].upd(d[v]);
rep(i , 0 , 1)
s[par[v]][i]+=min(min(h[c[v]].seg[1].a[i][0],h[c[v]].seg[1].a[i][1]),min(h[c[v]].seg[1].a[!i][0],h[c[v]].seg[1].a[!i][1])+1) ;
ch(par[v]) ;
}
void initialize(int N , vector <int> A , vector <int> B){
n = N ;
rep(i , 0 , n-2){
G[A[i]].pb(B[i]);
G[B[i]].pb(A[i]);
}
d1(1) ;
par[1] = 1;
h[1].az.pb(1) ;
c[1] = 1;
d2(1);
}
int ans(){
int f = inf ;
rep(i , 0 , 1){
rep(j , 0 ,1){
f =min(f , h[1].seg[1].a[i][j]) ;
}
}
return f ;
}
int neighbor(int v){
mark[v] = 0 ;
ch(v) ;
return ans() ;
}
int cat(int v){
mark[v] =1 ;
ch(v) ;
return ans() ;
}
int dog(int v){
mark[v]= 2 ;
ch(v);
return ans() ;
}
/*
signed main(){
ios::sync_with_stdio(0) ;cin.tie(0);
int n , q;
cin >> n >> q;
vector <int> a , b ;
rep(i , 1, n-1){
int v, u;
cin >> v >> u ;
a.pb(v);
b.pb(u) ;
}
initialize(n , a, b);
while(q--){
int t , v ;
cin >> t >> v;
if(t==0){
cout << neighbor(v) << "\n" ;
}else if(t==1){
cout << cat(v) << "\n" ;
}else{
cout << dog(v) << "\n" ;
}
}
}
*/
Compilation message
/usr/bin/ld: /tmp/ccfzHVfK.o: in function `main':
grader.cpp:(.text.startup+0x1f1): undefined reference to `initialize(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: grader.cpp:(.text.startup+0x229): undefined reference to `neighbor(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x26d): undefined reference to `dog(int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x311): undefined reference to `cat(int)'
collect2: error: ld returned 1 exit status
