তুমি লুকোচুরি খেলতে পারো তো?
একটা দলের মধ্যে একজনকে চোর বানানো হয়। এরপর সবাই ইচ্ছামতো এখানে সেখানে লুকিয়ে থাকে এবং চোরটির কাজ হয় অন্যদেরকে খুজে বের করা। চপ্পার এই খেলাটি তার বন্ধুদের সাথে খেলছিল এবং এখন তার লুকাবার সময় হয়েছে। এই খেলাটির সাধারণ নিয়ম হচ্ছে দূরে দূরে লুকানো, যেন সবাইকে একসাথে ধরে ফেলা না যায়। কিন্তু সবাই যদি অনেক দূরে লুকায়, তাহলে চোরের খুব মন খারাপ হয়, এবং খেলা নষ্ট হয়ে যায়।
আমাদের খেলার জায়গাটা একটা ট্রি-এর ন্যায় গঠন বিশিষ্ট। এখানে $n$
সংখ্যক লুকাবার জায়গা আছে, এবং $n-1$
সংখ্যক বিভিন্ন দৈর্ঘের রাস্তা দিয়ে তারা সংযুক্ত। ধর, $H$
হল সবাই যেখানে যেখানে লুকাবে সেই জায়গাগুলোর সেট। তাহলে এই সেট এর উৎকৃষ্টতার মান এভাবে নির্ণয় করা যায়ঃ
$f(H) = $
যেকোনো দুইটা স্থান $u, v$
এর দূরত্ব এর মধ্যে সর্বোচ্চ মান, যেখানে $u, v$
দুটোই সেট এর কোনো দুইটা স্থানের মধ্যবর্তী সংযোগকারী রাস্তার মধ্যে থাকে।
আমাদের ছোট্ট বন্ধু চপ্পার এর জন্য এতকিছু অনেক কঠিন হয়ে গিয়েছে। তাই তার তোমাকে প্রয়োজন $f(H)$
এর মান বের করতে।
প্রথম লাইনে দুটি পূর্ণসংখ্যা $n, m$
দেয়া হবে, যা নির্দেশ করে যথাক্রমে স্থানের সংখ্যা এবং কয়বার চপ্পার এর প্রশ্নের উত্তর দিতে হবে। এরপরে $n - 1$
সংখ্যক লাইনে $u, v, w$
দেয়া হবে, যা নির্দেশ করে $u$
থেকে $v$
তে $w$
দৈর্ঘের একটা রাস্তা আছে।
এরপর $m$
সংখ্যক লাইনে চপ্পার এর প্রশ্নগুলো দেয়া হবে। প্রতি লাইনের শুরুতে স্থান সংখ্যা $|H_i|$
দেয়া হবে, এরপর ততগুলো স্থান দেয়া হবে।
$ 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 $
$m$
সংখ্যক লাইন প্রিন্ট করবে, প্রত্যেক প্রশ্নের জন্য $f(H_i)$
এর মান।
Input | Output |
---|---|
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 |