Nayra doesn't like stories of people receiving random trees as birthday presents, but this time she received a tree as a present for her own birthday! After struggling for a day trying to figure out what to do with this tree, she asked Aryan for help. He gave her this problem. You are given a tree with N N vertices and weighted edges. It is rooted at vertex 1 1 . Define g ( u , v ) g ( u , v ) to be the maximum weight of an edge on the shortest path between vertex u u and vertex v v in this tree. Just calculating g ( u , v ) g ( u , v ) is too easy, so you have to process Q Q queries. In each query, you are given K K distinct vertices v 1 , v 2 , … , v K v 1 , v 2 , … , v K . You have to compute the sum of the g g -values of each pair of vertices among these K K , i.e, the value ∑ i = 1 K − 1 ∑ j = i + 1 K g ( v i , v j ) ∑ i = 1 K − 1 ∑ j = i + 1 K g ( v i , v j ) N...
Comments
Post a Comment