#include using namespace std; typedef long long ll; const int MAX_N = 100100; const int MAX_LOG= 20; ll n; ll par[MAX_LOG][MAX_N]; ll depth[MAX_N]; ll cost[MAX_N]; vector > G; vector U; void dfs(ll v,ll p, ll d, ll c){ par[0][v]=p; depth[v]=d; cost[v]=c+U[v]; for(auto nxt : G[v]){ if(nxt !=p) dfs(nxt, v, d+1, c+U[v]); } } void setPar(){ dfs(0,-1,0,0); for(ll i=0;idepth[b]) swap(a,b); for(ll i=0;i> i&1) b=par[i][b]; } if(a==b) return a; for(ll i=MAX_LOG-1;i>=0;i--){ if(par[i][a]!=par[i][b]){ a=par[i][a]; b=par[i][b]; } } return par[0][a]; } int main(){ scanf("%lld",&n); G.resize(n); for(ll i=0;i