You know how to play hide-and-seek, right?
In a group of kids, one of them is selected to be the seeker. All the other kids hide in different places and the seeker's task is to spot them without getting touched by any of the hiding players. Recently Chopper was playing this with his friends and guess what, it's time to hide! General strategy of this game is to hide in different places far apart, so that the seeker doesn't spot everyone at once. But staying too far can result in a never ending game, which everyone hates.
The playground can be specified as a tree structure with possible hiding locations connected with roads of different lengths. Let be the set of locations which hiders choose. The efficiency of this selection is defined by the function which can be calculated as follows:
= the maximum length between any two locations and such that they both belong to the shortest path between any atleast one pair of nodes in .
That was a lot to take in for our little friend Chopper. That's why he needs you to know the value of for several selections.
Input starts with two integers denoting the number of nodes in the tree and the number of selections made by Chopper. The follwoing lines each giving three integers denoting an edge connecting and with length .
The next lines will each describe a selection. Each line begins with the size of the selection , followed by the sequence of nodes which the hiders have chosen.
Print lines. For each selection print the value of .
8 3 1 2 2 2 3 3 2 4 5 2 5 7 2 6 11 3 7 1 3 8 2 3 7 8 5 2 1 2 6 4 5 6 1 2 3
12 2 18
Login to submit
Observe that f(H) is actually the maximum distance between two nodes in the given selection, because...