树链剖分。

const int N = 1e5 + 10 ;
struct node { int v , nxt ; } ;
node e[N << 1] ;
int head[N] , cnt = 0 ;
inline void Add(int u , int v) { e[++ cnt].v = v ; e[cnt].nxt = head[u] ; head[u] = cnt ; }
int size[N] , son[N] , d[N] ;
inline void Dfs1(int u) { size[u] = 1 ;
  for(register int i = head[u] ; i ; i = e[i].nxt) {
    int v = e[i].v ; if(v == fa[u]) continue ;
    d[v] = d[u] + 1 , fa[v] = u , Dfs1(v) ; size[u] += size[v] ;
    if(size[v] > size[son[u]]) son[u] = v ;
  }
}
int top[N] , id[N] , tot = 0 ;
inline void Dfs2(int u , int tp) { top[u] = tp , id[u] = ++ tot ;
  if(! son[u]) return ; Dfs2(son[u] , tp) ;
  for(register int i = head[u] ; i ; i = e[i].nxt) { int v = e[i].v ;
    if(v ^ fa[u] && v ^ son[u]) Dfs2(v , v) ;
  }
}