告诫后人

void dfs(int f, int u, int d) {
	fa[u][0]=f; dep[u]=d;
	for(auto& x:edge[u]) if(x!=f) dfs(u, x, d+1);
}
void init() {
	f(T,1,19) f(i,1,n) fa[i][T]=fa[fa[i][T-1]][T-1];
}
int lca(int x, int y) {
	if(x==y) return x;
	if(dep[x]<dep[y]) swap(x, y);
	d(i,0,19) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	//printf("x=%d, y=%d\n", x, y);
	if(x==y) return x;
	d(i,0,19) if(fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
	return fa[x][0];
}