void add(int u,int v){ e[idx] = v;ne[idx] = head[u];head[u] = idx++; } void dfs(int u,int father){ depth[u] = depth[father]+1; for(int i=0;i<=19;i++){ f[u][i+1] = f[u][f[u][i]]; } for(int i = head[u];i;i = ne[i]){ int v = e[i]; if( v == father) continue; f[v][0] = u; dfs(v,u); } } int LCA(int x,int y){ if(depth[x] < depth[y]) swap(x,y); for(int i=20;i>=0;i--){ if(depth[f[x][i]]>depth[y]) x = f[x][i]; if(x==y) return x; } for(int i =20;i>=0;i--){ if(f[x][i]!=f[y][i]){ x = f[x][i]; y = f[y][i]; } } return f[x][0]; //x.y是深度不同且最浅的子节点 }