help-INTRPATH
Can anybody please explain the given testcase?
And how to find out if two path contains only one vertex?
Please help guyz.
I have literally no idea about this question.
question link- https://www.codechef.com/JUNE19B/problems/INTRPATH
for diagram, refer to the question link.
You are given a tree (a connected undirected graph without cycles) with N vertices numbered 1 through N. For each pair of vertices u and v, let's denote the simple path between them by (u,v); the paths are undirected, so (u,v) is the same path as (v,u).
You should answer Q queries. In each query, you are given two vertices u and v. Then, for each simple path (a,b) in the tree, we define perfect intersection as follows:
Let's denote the sets of vertices in the paths (u,v) and (a,b) by S1 and S2 respectively (a path contains its endpoints too).
The path (a,b) intersects perfectly with (u,v) if |S1∩S2|=1, i.e. these paths have exactly one common vertex.
The answer to the query is the number of paths which intersect perfectly with the path (u,v).
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and Q.
Each of the next N−1 lines contains two space-separated integers u and v denoting that vertices u and v are connected by an edge.
Each of the next Q lines contains two space-separated integers u and v describing one query.
Output
For each query, print a single line containing one integer — the answer to this query.
Constraints
1≤T≤10
1≤N,Q≤3⋅105
1≤u,v≤N
Subtasks
Subtask #1 (10 points): 1≤N,Q≤100
Subtask #2 (20 points): 1≤N,Q≤1,000
Subtask #3 (70 points):
T≤5
1≤N≤250,000
1≤Q≤3⋅105
Example Input
1
6 2
1 2
1 3
1 4
2 5
2 6
4 5
1 3
Example Output
6
9
Explanation
Example case 1:
In the first query, the paths that intersect perfectly with the given path (4,5) are (1,1), (1,3), (2,2), (2,6), (4,4) and (5,5).
And how to find out if two path contains only one vertex?
Please help guyz.
I have literally no idea about this question.
question link- https://www.codechef.com/JUNE19B/problems/INTRPATH
for diagram, refer to the question link.
You are given a tree (a connected undirected graph without cycles) with N vertices numbered 1 through N. For each pair of vertices u and v, let's denote the simple path between them by (u,v); the paths are undirected, so (u,v) is the same path as (v,u).
You should answer Q queries. In each query, you are given two vertices u and v. Then, for each simple path (a,b) in the tree, we define perfect intersection as follows:
Let's denote the sets of vertices in the paths (u,v) and (a,b) by S1 and S2 respectively (a path contains its endpoints too).
The path (a,b) intersects perfectly with (u,v) if |S1∩S2|=1, i.e. these paths have exactly one common vertex.
The answer to the query is the number of paths which intersect perfectly with the path (u,v).
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and Q.
Each of the next N−1 lines contains two space-separated integers u and v denoting that vertices u and v are connected by an edge.
Each of the next Q lines contains two space-separated integers u and v describing one query.
Output
For each query, print a single line containing one integer — the answer to this query.
Constraints
1≤T≤10
1≤N,Q≤3⋅105
1≤u,v≤N
Subtasks
Subtask #1 (10 points): 1≤N,Q≤100
Subtask #2 (20 points): 1≤N,Q≤1,000
Subtask #3 (70 points):
T≤5
1≤N≤250,000
1≤Q≤3⋅105
Example Input
1
6 2
1 2
1 3
1 4
2 5
2 6
4 5
1 3
Example Output
6
9
Explanation
Example case 1:
In the first query, the paths that intersect perfectly with the given path (4,5) are (1,1), (1,3), (2,2), (2,6), (4,4) and (5,5).
Last edited on
For 1,3 in the sample input, the intersecting paths are (1,1) (3,3) (1,2) (1,5) (1,6) (4,1) (4,2) (4,5) and (4,6)
I haven't thought it all the way through, but the approach I'd take is to pick a node as the root of the tree. Then compute the number of subtrees from each node. From this, suspect you can compute the number of intersecting paths.
I haven't thought it all the way through, but the approach I'd take is to pick a node as the root of the tree. Then compute the number of subtrees from each node. From this, suspect you can compute the number of intersecting paths.
Can u plz explain more properly.
How can we write a program of this?
What sort of theory we will use?
Plz help.plz help with ur approach.
How can we write a program of this?
What sort of theory we will use?
Plz help.plz help with ur approach.
@dutch, idk if you are still reading this forum, you deleted the above example which you provided, but you got the output as 12 over there, i believe it should be 13, could you please re check if you dont mind.
Thanks.
Thanks.
Topic archived. No new replies allowed.