嗯~ o(*￣▽￣*)o
lca是树上两点的最近公共祖先。如果在同一个分支上就是更靠近根的那个点，否则就是大家一起向上走，第一次能都经过的那个点。
根据这两个性质，我们对于每次询问可以把一个向上走到根节点，标记走过的点。然后从另一个点向上走，直到遇到第一个标记过的点即为lca。
如果整个树是一个长链，这样的方法就会退化成一复杂度为n的算法。我们想一想如何优化成为log的策略。
假设两个节点到达lca的距离是m，那么这个m一定是可以被分解成一个二进制数的(废话)。我们可以好好利用一下这个性质。
设数组fa[i][k]表示节点i向上走2^k的父节点，d[i]表示i节点的深度。那么可以得到fa[i][0]是从i向上走1个到达的节点，即父节点。而且还可以得到fa[i][k]=fa[fa[i][k-1]][k-1]，因为二进制的定义。d[i]=d[fa[i][0]]+1应该不用再说了吧。
同时还可以维护许多数组表示其他性质，在topsort的时候需要自己加上。
//传入的参数即为你选中的根节点，实际上这个根节点选什么都一样 t=(int)log(n*1.0)/log(2.0)+1;//为最大的k void bfs(int now) {stack<int>q;q.push(now);d[now]=1;while(q.size()){int x=q.top();q.pop();for(int j=link[x];j!=0;j=o[j].next){int y=o[j].y;if(d[y])continue;q.push(y);d[y]=d[x]+1;fa[y][0]=x;for(int k=1;k<=t;k++)fa[y][k]=fa[fa[y][k-1]][k-1];//类似于动态规划的转移呦}} }
然后对于每个询问，先把x向上调整到于y同一深度，如果在同一个链上这个时候应该已经遇到了吧。如果没有遇到就可以俩人一起向上走，知道fa[x][k]==fa[y][k]的时候停下来。
int lca(int x,int y) {if(d[x]>d[y])swap(x,y);for(int k=t;k>=0;k--)if(d[fa[y][k]]>=d[x])y=fa[y][k];if(x==y)return x;for(int k=t;k>=0;k--)if(fa[x][k]!=fa[y][k])x=fa[x][k],y=fa[y][k];return fa[x][0]; }