、(最近公共祖先)已知一棵有根的多叉树,每次询问下求给定的两个点的最近公共祖先。其中输入的第一行 3 个整数为结点个数,询问次数,根节点序号。祖先结点:指一个结点本身或者它父节点的祖先。最近公共祖先:在一棵有根树中,对于任意两个结点的公共祖先中距离两者最近的结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include <iostream> #include <vector> using namespace std; const int MAXN = 500010; vector<int> edge[MAXN]; int depth[MAXN], lg[MAXN]; int pa[MAXN][22]; int n, m, r, x, y; void dfs(int fa, int sn, int dep) { depth[sn] = dep; pa[sn][0] = fa; for(int i = 1; ① ; i++) { pa[sn][i] = pa[pa[sn][i - 1]][i - 1]; } for(int i = 0; i < edge[sn].size(); i++) { int fn = edge[sn][i]; if (fn == fa) { continue; } dfs( ② ); } } int solve(int x, int y) { if (depth[x] < depth[y]) { swap(x, y); } while(depth[x] > depth[y]) { x = ③ ; } if(x == y) { return x; } for(int k = lg[depth[x]] - 1; k >= 0; --k) { if( ④ ) { x = pa[x][k], y = pa[y][k]; } } return pa[x][0]; } int main() { cin >> n >> m >> r; for(int i = 1; i <= n; i++) lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); for (int i = 0; i < n - 1; i++) { cin >> x >> y; edge[x].push_back(y); edge[y].push_back(x); } dfs( ⑤ ); while (m--) { cin >> x >> y; cout << solve(x, y) << endl; } return 0; } |
0 of 5 Questions completed
Questions:
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading…
You must sign in or sign up to start the quiz.
You must first complete the following:
0 of 5 Questions answered correctly
Your time:
Time has elapsed
You have reached 0 of 0 point(s), (0)
Earned Point(s): 0 of 0, (0)
0 Essay(s) Pending (Possible Point(s): 0)