poj1330Nearest Common Ancestors（水LCA）

这题只有一个询问，将一个节点的向上的标记下，再从另一个节点走一遍，遇到第一个被标记的就是整个算法的最坏时间复杂度是O(Q*n)，Q是询问的次数。

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int father[10010],f[10010];
 6 int main()
 7 {
 8     int g,i,j,k,n,a,b,t,c,d;
 9     cin>>t;
10     while(t--)
11     {
12         memset(f,0,sizeof(f));
13         cin>>n;
14         for(i = 1; i <= n ; i++)
15         father[i] = i;
16         for(i = 1 ; i < n ; i++)
17         {
18             cin>>a>>b;
19             father[b] = a;
20         }
21         cin>>c>>d;
22         f[c] = 1;
23         g = father[c];
24         f[g] = 1;
25         while(g!=father[g])
26         {
27             g = father[g];
28             f[g] = 1;
29         }
30         while(f[d]==0)
31         {
32             d = father[d];
33         }
34         cout<<d<<endl;
35     }
36     return 0;
37 }