Hide and Seek

peppermint BDYP & Duoblogger Home Qu...
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 $n$ possible hiding locations connected with $n-1$ roads of different lengths. Let $H$ be the set of locations which hiders choose. The efficiency of this selection is defined by the function $f(H)$ which can be calculated as follows:

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

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)$ for several selections.


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

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

$ 2 \leq n \leq 10^5, 1 \leq m \leq 10^5 $
$ 1 \leq u_i, v_i \leq n $, $ 1 \leq w_i \leq 10^6 $
$2 \leq |H_i| \leq n, \sum_{i = 1}^{m} |H_i| \leq 2 \times 10^5 $


Print $m$ lines. For each selection print the value of $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


Login to submit.


83% Solution Ratio
EgorKulikovEarliest, Apr '20
EgorKulikovFastest, 0.1s
vipghn2003Lightest, 16 MB
kzvd4729Shortest, 1400B
Toph uses cookies. By continuing you agree to our Cookie Policy.