题目大意：给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
整体步骤：1.使两个点深度相同；2.使两个点相同。
这两个步骤都可用倍增法进行优化。定义每个节点的Elder[i]为该节点的2^k（或者说是二进制中的1,10,100,1000...）辈祖先。求它时要利用性质：cur->Elder[i]==cur->Elder[i-1]->Elder[i-1]。具体步骤看代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int MAX_FA = 10, MAX_NODE = 500010, MAX_EDGE = MAX_NODE * 2; struct Node;
struct Edge; struct Node
{
int Id, Depth;
Edge *Head;
Node *Elder[MAX_FA];
}_nodes[MAX_NODE], *Root;
int TotNode; struct Edge
{
Node *From, *To;
Edge *Next;
}*_edges[MAX_EDGE];
int _edgeCnt; void Init(int root, int totNode)
{
_edgeCnt = 0;
TotNode = totNode;
Root = _nodes + root;
memset(_nodes, 0, sizeof(_nodes));
} Edge *NewEdge()
{
return _edges[++_edgeCnt] = new Edge();
} void AddEdge(Node *from, Node *to)
{
Edge *e = NewEdge();
e->From = from;
e->To = to;
e->Next = from->Head;
from->Head = e;
} void Build(int uId, int vId)
{
Node *u = _nodes + uId, *v = _nodes + vId;
u->Id = uId;
v->Id = vId;
AddEdge(u, v);
AddEdge(v, u);
} int Log2(int x)
{
int cnt = 0;
while (x / 2)
{
cnt++;
x /= 2;
}
return cnt;
} void Dfs(Node *cur, Edge *FromFa)
{
if(!FromFa)
cur->Depth = 1;
else
{
cur->Elder[0] = FromFa->From;
cur->Depth = cur->Elder[0]->Depth + 1;
for(int i=1; cur->Elder[i-1]->Elder[i-1]; i++)
cur->Elder[i] = cur->Elder[i-1]->Elder[i-1];
}
for(Edge *e = cur->Head; e; e=e->Next)
if(e->To!=cur->Elder[0])
Dfs(e->To, e);
} void DfsStart()
{
Dfs(Root, NULL);
} Node *Lca(Node *deep, Node *high)
{
if (deep->Depth < high->Depth)
swap(deep, high);
int len = deep->Depth - high->Depth;
for(int k=0; len; k++)
{
if((1 << k) & len)
{
deep=deep->Elder[k];
len -= (1 << k);//把len二进制中当前的1去掉
}
}
if (deep == high)
return deep;
for (int k = Log2(deep->Depth); k >= 0; k--)
{
if (deep->Elder[k] != high->Elder[k])
{
deep = deep->Elder[k];
high = high->Elder[k];
}
}
return deep->Elder[0];
} int main()
{
int totNode, totQ, rootId, uId, vId, id1, id2;
scanf("%d%d%d", &totNode, &totQ, &rootId);
Init(rootId, totNode);
for (int i = 1; i < totNode; i++)
{
scanf("%d%d", &uId, &vId);
Build(uId, vId);
}
DfsStart();
for (int i = 1; i <= totQ; i++)
{
scanf("%d%d", &id1, &id2);
printf("%d\n", Lca(id1 + _nodes, id2 + _nodes)->Id);
}
return 0;
}
对Lca中for循环正确性的解释：每个整数都可以表示为sum(2^k)。所以以此方式可以到达一个节点的任意辈祖先。
注意：
- k初值有log。
- 树的深度和高度要区分开来。
- Dfs时一开始循环中的判断cur->[k-1]!=NULL是为了处理根节点。