Problem of the day
U V W
Input: ‘N’ = 4, ‘ROADS’ = [[1, 2, 2], [1, 3, 3], [2, 4, 3]], ‘Q’ = 1, ‘Queries’ = [[3, 4, 2]]
Output: YES
If we remove the road between 2 and 4 and add the current road of queries then the sum becomes 7 which previously was 8.
The first line will contain the integer 'T', denoting the number of test cases.
The next line contains a single integer ‘N’ representing the number of villages.
The next ‘N’-1 lines contain three integers ‘U’, ‘V’, and ‘W’ representing the villages ‘U’ and ‘V’ where a road of distance ‘W’ is made.
The next line contains an integer ‘Q’ representing the number of queries.
The next ‘Q’ lines contain ‘U’, ‘V’, and ‘W’ representing the query of making a road between villages ‘U’, ‘V’ with a distance ‘W’.
For each test query, you should output ‘YES’ if the total distance strictly reduces else print ‘NO’.
You don't need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= N <= 10^5
1 <= W <= 10^9
1 <= U, V <= N
1 <= Q <= 10^5
Time Limit: 1 sec
2
4
1 2 2
1 3 3
2 4 3
1
3 4 1
3
1 2 4
2 3 5
2
1 3 2
1 2 5
YES
YES NO
For the first test case:-
If we remove the road between 2 and 4 and add the current road of query then the sum becomes 6 which previously was 8 so the answer is ‘YES’.
For the second test case:-
Initially, the total distance is 9.
For the first query if we add the road between villages 1 and 3 with the distance 2 and remove the road between 2 and 3 which has a distance of 5 so now the total distance of all the roads is 6 which is less than 9 so the answer is ‘YES’.
For the second query, the initial road between 1 and 2 has a distance of 4 but now we are trying to create a road of distance 5 which will increase the total distance to 10 so the answer is ‘NO’.
2
7
1 2 3
1 3 3
3 4 2
3 5 3
4 6 4
5 7 5
4
1 4 2
4 7 10
6 7 1
1 5 12
4
1 2 1
2 3 1
3 4 1
5
1 2 1
1 3 2
2 3 5
3 1 1
3 4 2
YES NO YES NO
NO NO NO NO NO