poj1330Nearest Common Ancestors(LCA小结)
题目请戳这里
题目大意：意如其名。
题目分析：本题只有一个查询，所以可以各种乱搞过去。
不过对于菜鸟而言，还是老老实实练习一下LCA算法。
LCA有很多经典的算法。按工作方式分在线和离线2种。
tarjan算法是经典的离线算法。这篇博客讲的太好懂了，我也不好意思班门弄斧，具体戳进去看看就会明白。重点是那个插图，一看秒懂。
在线算法主要有倍增算法和转RMQ算法。
另外LCA还有2种更为高效的O(n)-O(1)算法。一种请戳这里，另一种其实就是先将LCA转化成RMQ，再利用笛卡尔树O（n）预处理，O（1）回答，具体可以戳这里。
后两种O(n)算法还没有仔细研究，大致看了下，不是很明白，但是感觉很厉害的样子。mark一下，以后抽时间学习一下。
下面给出本题的前3种算法具体实现：
1：tarjan算法（虽然对本题来说有点奢侈了。。）
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 10005;int dp[N][20],deep[N];struct node{ int to,next;}e[N];int n,num,p,q;int head[N],in[N];void build(int s,int ed){ e[num].to = ed; e[num].next = head[s]; head[s] = num ++;}void dfs(int cur,int fa){ deep[cur] = deep[fa] + 1; dp[cur][0] = fa; int i; for(i = 1;i < 18;i ++) dp[cur][i] = dp[dp[cur][i - 1]][i - 1]; for(i = head[cur];i != -1;i = e[i].next) { dfs(e[i].to,cur); }}int lca(){ if(deep[p] < deep[q]) swap(p,q); int i,j; for(j = deep[p] - deep[q],i = 0;j;j >>= 1,i ++) { if(j&1) p = dp[p][i]; } if(p == q) return q; for(i = 18;i >= 0;i --) { if(dp[p][i] != dp[q][i]) { p = dp[p][i]; q = dp[q][i]; } } return dp[q][0];}void solve(){ int i; memset(deep,0,sizeof(deep)); for(i = 1;i <= n;i ++) if(in[i] == 0) break; dfs(i,0); printf("%d\n",lca());}int main(){ int t,i,a,b; freopen("in.txt","r",stdin); scanf("%d",&t); while(t --) { scanf("%d",&n); num = 0; memset(head,-1,sizeof(head)); memset(in,0,sizeof(in)); for(i = 1;i < n;i ++) { scanf("%d%d",&a,&b); build(a,b); in[b] ++; } scanf("%d%d",&p,&q); solve(); } return 0;}