題目請戳這里

題目大意：意如其名。

題目分析：本題只有一個查詢，所以可以各種亂搞過去。

不過對于菜鳥而言，還是老老實實練習(xí)一下LCA算法。

LCA有很多經(jīng)典的算法。按工作方式分在線和離線2種。

tarjan算法是經(jīng)典的離線算法。這篇博客講的太好懂了，我也不好意思班門弄斧，具體戳進去看看就會明白。重點是那個插圖，一看秒懂。

在線算法主要有倍增算法和轉(zhuǎn)RMQ算法。

另外LCA還有2種更為高效的O(n)-O(1)算法。一種請戳這里，另一種其實就是先將LCA轉(zhuǎn)化成RMQ，再利用笛卡爾樹O（n）預(yù)處理，O（1）回答，具體可以戳這里。

后兩種O(n)算法還沒有仔細研究，大致看了下，不是很明白，但是感覺很厲害的樣子。mark一下，以后抽時間學(xué)習(xí)一下。

下面給出本題的前3種算法具體實現(xiàn)：

1：tarjan算法（雖然對本題來說有點奢侈了。。）

?

#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 10005; struct node {int to,next; }e[N]; int head[N],set[N],fa[N],in[N]; bool vis[N]; int n,num,p,q; void build(int s,int ed) {e[num].to = ed;e[num].next = head[s];head[s] = num ++; } void init() {num = 0;memset(head,-1,sizeof(head));memset(in,0,sizeof(in)); } int find(int x) {int rt = x;while(set[rt] != rt)rt = set[rt];int pa = set[x];while(pa != rt){set[x] = rt;x = pa;pa = set[x];}return rt; } void bing(int a,int b) {int ra = find(a);int rb = find(b);if(ra != rb)set[rb] = ra; } void dfs(int cur) {fa[cur] = cur;set[cur] = cur;int i;for(i = head[cur];i != -1;i = e[i].next){dfs(e[i].to);bing(cur,e[i].to);fa[find(cur)] = cur;}vis[cur] = true;if((p == cur && vis[q]))printf("%d\n",fa[find(q)]);if((q == cur && vis[p]))printf("%d\n",fa[find(p)]); } void tarjan() {int i;memset(vis,false,sizeof(vis));for(i = 1;i <= n;i ++)if(in[i] == 0)break;dfs(i); } int main() {int t;int i,a,b;scanf("%d",&t);while(t --){scanf("%d",&n);init();for(i = 1;i < n;i ++){scanf("%d%d",&a,&b);build(a,b);in[b] ++;}scanf("%d%d",&p,&q);tarjan();}return 0; }

2：LCA轉(zhuǎn)RMQ，再st算法：

?

?

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N = 20005;int dep[N],pos[N],seq[N],first[N],in[N]; int dp[N][20]; struct node {int to,next; }e[N]; int head[N]; int n,num,p,q,id; void build(int s,int ed) {e[num].to = ed;e[num].next = head[s];head[s] = num ++; }void dfs(int cur,int deep) {dep[cur] = deep;first[cur] = id;pos[id] = cur;seq[id ++] = dep[cur];int i;for(i = head[cur];i != -1;i = e[i].next){dfs(e[i].to,deep + 1);pos[id] = cur;seq[id ++] = dep[cur];} } int rmq() {int i,j;for(i = 1;i <= id;i ++)dp[i][0] = i;for(j = 1;(1<<j) <= id;j ++){for(i = 1;(i + (1<<(j - 1))) <= id;i ++)if(seq[dp[i][j - 1]] < seq[dp[i + (1<<(j - 1))][j - 1]])dp[i][j] = dp[i][j - 1];elsedp[i][j] = dp[i + (1<<(j - 1))][j - 1];}int tp = first[p];int tq = first[q];if(tp > tq)swap(tp,tq);int k = floor(log((double)(tq - tp + 1))/log(2.0));int tmp;if(seq[dp[tp][k]] < seq[dp[tq - (1<<k) + 1][k]])tmp = dp[tp][k];elsetmp = dp[tq - (1<<k) + 1][k];return pos[tmp]; } void solve() {int i;id = 1;for(i = 1;i <= n;i ++)if(in[i] == 0)break;dfs(i,0);id --;printf("%d\n",rmq()); } int main() {int i,a,b,t;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; }

3：倍增算法：

?

?

#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; }

?

?

總結(jié)

以上是生活随笔為你收集整理的poj1330Nearest Common Ancestors(LCA小结)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。