#include using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000001 struct HLD{ vector sz,parent,depth,root,pos; vector arr; HLD(vector> &E){ sz.resize(E.size(),1); parent.resize(E.size(),0); depth.resize(E.size(),0); root.resize(E.size(),0); pos.resize(E.size(),0); dfs(0,-1,E); dfs2(0,-1,E,0); } void dfs(int now,int p,vector> &E){ parent[now] = p; if(p==-1){ depth[now] = 0; } else{ depth[now] = depth[p]+1; } for(int i=0;i> &E,int r){ pos[now] = arr.size(); arr.push_back(now); root[now] = r; int maxi = 0; int ind = -1; for(int i=0;i> query(int u,int v){ vector> ret; int t = 0; while(root[u]!=root[v]){ if(depth[root[u]] <= depth[root[v]]){ ret.insert(ret.begin()+t,{pos[root[v]], pos[v]}); v = parent[root[v]]; } else{ ret.insert(ret.begin()+t,{pos[u],pos[root[u]]}); u = parent[root[u]]; t++; } } ret.insert(ret.begin()+t,{pos[u],pos[v]}); return ret; } }; template struct segtree{ F func; vector v; int n; T init_value; segtree(int sz,F f,T iv):func(f){ init_value = iv; n=1; while(true){ if(n>=sz)break; n*=2; } v.resize(2*n,init_value); for(int i=n-1;i>=0;i--){ v[i]=func(v[i<<1],v[(i<<1)+1]); } } segtree(vector &x,F f,T iv):func(f){ init_value = iv; n=1; while(true){ if(n>=x.size())break; n*=2; } v.resize(2*n,init_value); for(int i=0;i=0;i--){ v[i]=func(v[i<<1],v[(i<<1)+1]); } } void update(int x,T val){ x+=n; v[x]=val; while(x>0){ x>>=1; v[x]=func(v[x<<1],v[(x<<1)+1]); } } T query(int l,int r){ if(l>=r)return init_value; l+=n; r+=n; T res1 = init_value; T res2 = init_value; while(true){ if(l&1){ res1=func(res1,v[l++]); } if(r&1){ res2=func(v[--r],res2); } if(l>=r)break; l>>=1;r>>=1; } return func(res1,res2); } void show(){ int n = 1; for(int i=1;i> E; int cnt = 0; map,int> mp; vector ans; vector> get_fixedE(vector> E){ vector> ret(2*N-1,vector()); int t = N; for(int i=0;ito)continue; mp[{i,to}]=t; mp[{to,i}]=t; ret[i].push_back(t); ret[t].push_back(i); ret[to].push_back(t); ret[t].push_back(to); t++; } } return ret; } int get_dis(int u,int v,auto &H,auto &S){ auto V = H.query(u,v); int ret = 0; for(auto a:V){ int l = a.first; int r = a.second; if(l>r)swap(l,r); ret += S.query(l,r+1); } return ret; } void dfs0(auto &E,int now,int p,auto &H,auto &S1,auto &S2){ for(int i=0;i Temp; for(int i=0;i temp; for(int j=0;j=2){ int x = E[now][i-1]; int nn = mp[{now,x}]; int fnn = H.pos[nn]; S2.update(fnn,1); } dfs1(E,to,now,H,S0,S1,S2); if(S1.query(fn,fn+1)==1)cnt--; S1.update(fn,0); if(E[to][0]!=now){ cnt++; S1.update(fn,1); } for(int j=0;j()); for(int i=0;i> fixedE = get_fixedE(E); HLD H(fixedE); vector d0(2*N-1,0); vector d1 = d0,d2 = d0; for(int i=N;i<2*N-1;i++)d0[i] = 1; { vector temp(2*N-1); for(int i=0;i<2*N-1;i++){ temp[i] = d0[H.arr[i]]; } d0 = temp; } auto f = [](int a,int b){ return a+b; }; segtree S0(d0,f,0),S1(d1,f,0),S2(d2,f,0); dfs0(E,0,-1,H,S1,S2); ans.resize(N,false); dfs1(E,0,-1,H,S0,S1,S2); for(int i=0;i