Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hide and Seek

By peppermint · Limits 1.5s, 256 MB

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 nn possible hiding locations connected with n1n-1 roads of different lengths. Let HH be the set of locations which hiders choose. The efficiency of this selection is defined by the function f(H)f(H) which can be calculated as follows:

f(H)f(H) = the maximum length between any two locations uu and vv such that they both belong to the shortest path between any atleast one pair of nodes in HH.

That was a lot to take in for our little friend Chopper. That's why he needs you to know the value of f(H)f(H) for several selections.


Input starts with two integers n,mn, m denoting the number of nodes in the tree and the number of selections made by Chopper. The follwoing n1n - 1 lines each giving three integers u,v,wu, v, w denoting an edge connecting uu and vv with length ww.

The next mm lines will each describe a selection. Each line begins with the size of the selection Hi|H_i|, followed by the sequence of nodes which the hiders have chosen.

2n105,1m105 2 \leq n \leq 10^5, 1 \leq m \leq 10^5
1ui,vin 1 \leq u_i, v_i \leq n , 1wi106 1 \leq w_i \leq 10^6
2Hin,i=1mHi2×1052 \leq |H_i| \leq n, \sum_{i = 1}^{m} |H_i| \leq 2 \times 10^5


Print mm lines. For each selection print the value of f(Hi)f(H_i).


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



86% Solution Ratio

EgorKulikovEarliest, Apr '20

EgorKulikovFastest, 0.1s

vipghn2003Lightest, 16 MB

kzvd4729Shortest, 1400B


Login to submit


Observe that f(H) is actually the maximum distance between two nodes in the given selection, because...

Related Contests