LCA Query On Tree
Practice
5 (1 votes)
Medium
Problem
18% Success 460 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code
Given a tree with N nodes rooted at node 1 and a node X.You have to count the number of pairs of nodes such that they have node X as their lowest common ancestor.
Input:
The first line of the input file contains 2 integers N and node X.
Each of the next n-1 lines contains 2 integers u and v denoting that there is an edge between node u and v.
Output:
The output should contain a single integer, the answer to the problem.
Constraints:
1<=N<=100000
1<=X,u,v<=n
Sample Input
4 4 1 2 1 3 2 4
Sample Output
0
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Submissions
Please login to view your submissions
Similar Problems
Points:30
1 votes
Tags:
Data StructuresTreesLowest Common Ancestor
Points:30
3 votes
Tags:
TreesLowest Common AncestorData Structures
Points:30
4 votes
Tags:
Dynamic ProgrammingModular arithmeticImplementationTreesData StructuresC++Lowest Common AncestorBit manipulation
Editorial
No editorial available for this problem.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor