There is a tree consisting of N nodes and N-1 edges. Each node is numbered from 1 to N. Given two nodes A and B, the task is to find the Lowest Common Ancestor (LCA) of these two nodes. However, since the tree can be very large, an efficient algorithm needs to be used.<\/p>\n
\n7\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n4 5\n3\n4 5\n4 6\n5 6\n<\/pre>\nExample Output<\/h2>\n
\n2\n1\n3\n<\/pre>\nSolution Strategy<\/h2>\n
To efficiently find the Lowest Common Ancestor, we will use the following approach.<\/p>\n
\n
- Representation of Tree Structure:<\/strong> The tree is represented using an adjacency list. Each node is connected to its parent and children, thus forming the tree.<\/li>\n
- Creating Depth and Parent Arrays using DFS:<\/strong> We use the Depth First Search (DFS) algorithm to determine the depth of each node and to record the parent nodes. This information is essential for finding the LCA.<\/li>\n
- Binary Lifting:<\/strong> To efficiently find the LCA, we use the binary lifting method (Fast LCA). The process involves aligning the depths of the two nodes and finding their common ancestor.<\/li>\n<\/ul>\n
Implementation Steps<\/h2>\n
1. Creating Tree Structure<\/h3>\n
First, we build the tree based on the edge information. In this process, we define the relationship between parents and children and represent it through an adjacency list.<\/p>\n
2. Generating Depth and Parent Arrays using DFS<\/h3>\n
Now, we need to record the depth and parent of each node using DFS. The depth indicates how far each node is from the root, and the parent information is crucial for finding the LCA in the next step.<\/p>\n
3. Implementing LCA Function<\/h3>\n
We implement a function to find the Lowest Common Ancestor of two nodes using binary lifting. This function compares the depths of the two nodes and adjusts the depths if needed, subsequently finding their ancestors.<\/p>\n
4. Processing Queries<\/h3>\n
For each query, we find and output the LCA of the given two nodes A and B.<\/p>\n
Code Implementation<\/h2>\n
\n#include\n#include \n#include \n#include \n\nusing namespace std;\n\nconst int MAX_N = 100000;\nconst int LOG = 17; \/\/ log2(100000) \u2248 16.61\n\nint parent[MAX_N + 1][LOG + 1]; \/\/ Parent array\nint depth[MAX_N + 1]; \/\/ Depth array\nvector tree[MAX_N + 1]; \/\/ Tree in adjacency list format\nint N;\n\nvoid dfs(int node, int par, int d) {\n depth[node] = d;\n parent[node][0] = par;\n for (int i = 1; i <= LOG; i++) {\n parent[node][i] = parent[parent[node][i - 1]][i - 1];\n }\n \n for (int child : tree[node]) {\n if (child != par) {\n dfs(child, node, d + 1);\n }\n }\n}\n\nint lca(int a, int b) {\n if (depth[a] < depth[b]) swap(a, b);\n\n for (int i = LOG; i >= 0; i--) {\n if (depth[parent[a][i]] >= depth[b]) {\n a = parent[a][i];\n }\n }\n\n if (a == b) return a;\n\n for (int i = LOG; i >= 0; i--) {\n if (parent[a][i] != parent[b][i]) {\n a = parent[a][i];\n b = parent[b][i];\n }\n }\n\n return parent[a][0];\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n\n cin >> N;\n for (int i = 0; i < N - 1; i++) {\n int u, v;\n cin >> u >> v;\n tree[u].push_back(v);\n tree[v].push_back(u);\n }\n\n dfs(1, 0, 0); \/\/ Root is 1\n int Q;\n cin >> Q;\n\n for (int i = 0; i < Q; i++) {\n int a, b;\n cin >> a >> b;\n cout << lca(a, b) << '\\n';\n }\n\n return 0;\n}\n<\/int><\/cmath><\/algorithm><\/vector><\/iostream><\/pre>\n Conclusion<\/h2>\n
This problem helps understand the use of DFS and binary lifting methods to find the Lowest Common Ancestor. Learning various algorithms to process trees and enhancing coding skills will be greatly beneficial. Practicing different approaches to explore tree structures and find the LCA based on the given problem will be very useful for coding test preparation.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"