Given a tree with N vertices and N-1 undirected edges, where each edge has a weight associated with it.
gcd(A,B) is gcd of weight of all the edges in the path from A to B.
len(A,B) is number of edges in path from A to B.
You have to maximise gcd(A,B) * len(A,B) over all possible pairs A,B.
Input
N - number of nodes
Next N-1 lines contains 3 integers a,b,c representing there is an edge between a and b of weight c.
Output
In a single line print the maximum value.
Constraints
1<=T<=10
2 <= N <= 100000
c <= 100000
Sample Input
1
3
1 2 10
2 3 4
Sample output
10
1 Like
please explain your solution Aman, I have a complicated solution which is based on divide and conquer idea on tree using center.
Yes praveen my solution is also based on centroid decomposition of tree.
Problem : To find max of gcd*len for among paths.
Idea: divide and conquer on tree using its center (centroid decomposition (link)).
If u remove the center then the tree is divided into various subtree where max size of each subtree is less than N/2, thus we can ensure that a maximum of log(N) levels of decomposition will be there and at every level there are N nodes.
Now In a subtree assume its center to be the root of this subtree.
Our problem is now reduced to finding max length for all possible gcd containing root.
This can be done in n*log(n) time where n is the number of nodes in the subtree.
suppose root have k child, then the 2 nodes which are selected(ie path between these nodes gives required max) should be in subtree of 2 different child such that there path contains the root.
now keep min and 2nd min length for each gcd across the k child, but within a child only max length is considered.
answer is maximum of gcd*(min + 2nd min) for all possible gcd.
total time complexity : n*(log(n))^2
I was thinking of the same problem in arrays instead of trees and that also seems like a good problem(assuming my solution is correct). So if we think that this problem is too complicated to be solved in small amount of time we can give the array variation of problem.
I dont know much about the centroid decomposition so I cannot guess the complexity of this problem.
Actually this problem is inspired from array version only