<题目链接>
题目大意:
给出一棵树,问任意两个点的最近公共祖先的编号。
解题分析:
LCA模板题,下面用的是树上倍增求解。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; ; const int INF = 0x3f3f3f3f; struct Edge{ int to, next; }edge[N<<]; int n,cnt, head[N], in[N]; ]; void add_edge(int v, int u){ edge[cnt].to = u, edge[cnt].next = head[v], head[v] = cnt++; } void dfs(int u, int fa){ //得到所有节点的深度 ; i = edge[i].next){ int v = edge[i].to; if(v == fa) continue; if(!dep[v]){ dep[v] = dep[u] + ; f[v][] = u; dfs(v, u); } } } void init(){ //树上倍增预处理 ; (<<j) <= n; j++) ; i <= n; i++) f[i][j] = f[f[i][j-]][j-]; } int LCA(int v, int u){ if(dep[v] < dep[u])swap(v, u); //v为深度更深的节点 int d = dep[v] - dep[u]; ; (d>>i) != ; i++) ) v = f[v][i]; //以上的操作是处理较深的节点,使两节点深度一致 if(v == u) return v; //如果深度一致时,两节点相同,那么直接返回即可 ;i>= ;i--) if(f[v][i] != f[u][i]) //跳2^i步不一样,就跳,否则不跳 v = f[v][i],u = f[u][i]; //两点一起向上跳2^i步 ]; //经证明,上述操作做完,两点的LCA都在上一层,所以再走一步即可 } int main(){ int t, a, b; scanf("%d", &t); while(t--){ scanf("%d", &n); cnt = ; memset(head, -, sizeof head); memset(, sizeof in); ; i < n; i++){ scanf("%d%d", &a, &b); add_edge(a, b); in[b]++; } memset(dep, , sizeof dep); int root; ; i <= n; i++) if(!in[i]) root = i; dep[root] = ; dfs(root, -); init(); //注意这里init要放在dfs后面,因为f[i][0]需要通过dfs预处理得到 scanf("%d%d", &a, &b); printf("%d\n", LCA(a, b)); } ; }
2018-10-18