| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 19919 | Accepted: 10544 |
Description
In the figure, each node is labeled with an integer from {1,
2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node
y if node x is in the path between the root and node y. For example,
node 4 is an ancestor of node 16. Node 10 is also an ancestor of node
16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of
node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6,
and 7 are the ancestors of node 7. A node x is called a common ancestor
of two different nodes y and z if node x is an ancestor of node y and an
ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of
nodes 16 and 7. A node x is called the nearest common ancestor of nodes y
and z if x is a common ancestor of y and z and nearest to y and z among
their common ancestors. Hence, the nearest common ancestor of nodes 16
and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.
For other examples, the nearest common ancestor of nodes 2 and 3 is
node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and
the nearest common ancestor of nodes 4 and 12 is node 4. In the last
example, if y is an ancestor of z, then the nearest common ancestor of y
and z is y.
Write a program that finds the nearest common ancestor of two distinct nodes in a tree.
Input
input consists of T test cases. The number of test cases (T) is given in
the first line of the input file. Each test case starts with a line
containing an integer N , the number of nodes in a tree,
2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N.
Each of the next N -1 lines contains a pair of integers that represent
an edge --the first integer is the parent node of the second integer.
Note that a tree with N nodes has exactly N - 1 edges. The last line of
each test case contains two distinct integers whose nearest common
ancestor is to be computed.
Output
Sample Input
2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5
Sample Output
4
3 单次的lca，每次从u和v的depth较深的开始往上面找，然后如果一样就跳出，不一样继续找
复杂度depth[u]+depth[v]
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 10019
#define eps 1e-9
const int inf=0x7fffffff; //无限大
int flag1[maxn];
int flag2[maxn];
vector<int> G[maxn];//图的邻接表表示方法
int root;//根节点的编号 int parent[maxn];//父亲节点
int depth[maxn];//节点的深度 void dfs(int v,int p,int d)
{
parent[v]=p;
depth[v]=d;
for(int i=;i<G[v].size();i++)
{
if(G[v][i]!=p)
dfs(G[v][i],v,d+);
}
} void init()
{
dfs(root,,-);
} int lca(int u,int v)
{
while(depth[u]>depth[v])
u=parent[u];
while(depth[v]>depth[u])
v=parent[v];
while(u!=v)
{
u=parent[u];
v=parent[v];
}
return u;
} int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=;i<n;i++)
G[i].clear();
memset(parent,,sizeof(parent));
memset(depth,,sizeof(depth));
memset(flag1,,sizeof(flag1));
memset(flag2,,sizeof(flag2));
int a,b;
for(int i=;i<n-;i++)
{
cin>>a>>b;
G[a].push_back(b);
flag1[a]=;
flag2[b]=;
}
for(int i=;i<=n;i++)
{
if(flag1[i]==&&flag2[i]==)
{
root=i;
break;
}
}
init();
cin>>a>>b;
cout<<lca(a,b)<<endl;
}
}