문제
정점이 $N$개인 트리가 주어진다. 각 정점은 1번부터 $N$번까지 차례대로 번호가 부여되어 있다. $i$번째 간선은 $A_i$번 정점과 $B_i$번 정점을 연결하며, 가중치는 $C_i$다. $(1 \leq i < N)$
트리에서 두 정점 사이의 거리는 그 둘을 잇는 최단경로 상의 간선의 가중치의 최댓값으로 정의한다. 단, 같은 두 정점 사이의 거리는 0으로 정의한다.
트리에 사는 사람들이 $N$개의 모임을 개최하려 한다. $i$번째 모임에는 1 이상 $i$ 이하의 번호를 가진 정점에 사는 사람들이 참석한다. 올해에는 코로나바이러스 전파 상황을 고려해 모임을 $X$개의 장소에서 각자 모인 후, 인터넷으로 진행하기로 했다. 각 모임은 트리 상의 서로 다른 $X$개의 정점 $v_1,\cdots,v_X$에서 이루어진다. 모임마다 고르는 정점은 독립적이다. 정점들이 정해지면 각 사람은 $v_1, \cdots, v_X$ 중 필요한 이동 거리가 최소인 정점 중 하나를 골라 이동하게 된다.
코로나바이러스 전파 상황에 따라 $X$의 값을 1ドル$부터 $K$까지의 값 중 하나로 정하기로 하였다. 모임을 미리 준비하기 위해 각 모임에 대해, $X$의 값이 1ドル$일 때부터 $K$일 때까지 사람들이 이동하는 거리의 최댓값의 최솟값의 합을 구하는 프로그램을 작성하시오.
출력
첫 번째 줄부터 $N$개의 줄에 걸쳐, 답을 차례대로 출력한다. $i$번째 줄에는 $i$번째 모임에 대한 답을 출력한다 $(1 \leq i \leq N)$.
예제 출력 1
복사
0
4
13
21
23
23
30
31
33
34
예제 출력 2
복사
0
8
14
16
16
16
18
18
W3sicHJvYmxlbV9pZCI6IjIwNTU5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODE1XHVhZTMwIFx1YmFhOFx1Yzc4NCAyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWM4MTBcdWM3NzQgJE4kXHVhYzFjXHVjNzc4IFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWM4MTBcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCAkTiRcdWJjODhcdWFlNGNcdWM5YzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkODBcdWM1ZWNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHVhYzA0XHVjMTIwXHVjNzQwICRBX2kkXHViYzg4IFx1YzgxNVx1YzgxMFx1YWNmYyAkQl9pJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViYTcwLCBcdWFjMDBcdWM5MTFcdWNlNThcdWIyOTQgJENfaSRcdWIyZTQuICQoMSBcXGxlcSBpICZsdDsgTikkPFwvcD5cclxuXHJcbjxwPlx1ZDJiOFx1YjlhY1x1YzVkMFx1YzExYyBcdWI0NTAgXHVjODE1XHVjODEwIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVhZGY4IFx1YjQ1OFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjIFx1YzBjMVx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhYzAwXHVjOTExXHVjZTU4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWM4MTVcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCAwXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmI4XHViOWFjXHVjNWQwIFx1YzBhY1x1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgJE4kXHVhYzFjXHVjNzU4IFx1YmFhOFx1Yzc4NFx1Yzc0NCBcdWFjMWNcdWNkNWNcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHViYWE4XHVjNzg0XHVjNWQwXHViMjk0IDEgXHVjNzc0XHVjMGMxICRpJCBcdWM3NzRcdWQ1NThcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljNCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHVjMGFjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWNjMzhcdWMxMWRcdWQ1NWNcdWIyZTQuIFx1YzYyY1x1ZDU3NFx1YzVkMFx1YjI5NCBcdWNmNTRcdWI4NWNcdWIwOThcdWJjMTRcdWM3NzRcdWI3ZWNcdWMyYTQgXHVjODA0XHVkMzBjIFx1YzBjMVx1ZDY2OVx1Yzc0NCBcdWFjZTBcdWI4MjRcdWQ1NzQgXHViYWE4XHVjNzg0XHVjNzQ0ICRYJFx1YWMxY1x1Yzc1OCBcdWM3YTVcdWMxOGNcdWM1ZDBcdWMxMWMgXHVhYzAxXHVjNzkwIFx1YmFhOFx1Yzc3OCBcdWQ2YzQsIFx1Yzc3OFx1ZDEzMFx1YjEzN1x1YzczY1x1Yjg1YyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWFjMDEgXHViYWE4XHVjNzg0XHVjNzQwIFx1ZDJiOFx1YjlhYyBcdWMwYzFcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCAkWCRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwICR2XzEsXFxjZG90cyx2X1gkXHVjNWQwXHVjMTFjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHVjNzg0XHViOWM4XHViMmU0IFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NDAgXHViM2M1XHViOWJkXHVjODAxXHVjNzc0XHViMmU0LiBcdWM4MTVcdWM4MTBcdWI0ZTRcdWM3NzQgXHVjODE1XHVkNTc0XHVjOWMwXHViYTc0IFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NDAgJHZfMSwgXFxjZG90cywgdl9YJCBcdWM5MTEgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzc3NFx1YjNkOSBcdWFjNzBcdWI5YWNcdWFjMDAgXHVjZDVjXHVjMThjXHVjNzc4IFx1YzgxNVx1YzgxMCBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YWNlOFx1Yjc3YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNmNTRcdWI4NWNcdWIwOThcdWJjMTRcdWM3NzRcdWI3ZWNcdWMyYTQgXHVjODA0XHVkMzBjIFx1YzBjMVx1ZDY2OVx1YzVkMCBcdWI1MzBcdWI3N2MgJFgkXHVjNzU4IFx1YWMxMlx1Yzc0NCAkMSRcdWJkODBcdWQxMzAgJEskXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWMxMiBcdWM5MTEgXHVkNTU4XHViMDk4XHViODVjIFx1YzgxNVx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YmFhOFx1Yzc4NFx1Yzc0NCBcdWJiZjhcdWI5YWMgXHVjOTAwXHViZTQ0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjMDEgXHViYWE4XHVjNzg0XHVjNWQwIFx1YjMwMFx1ZDU3NCwgJFgkXHVjNzU4IFx1YWMxMlx1Yzc3NCAkMSRcdWM3N2MgXHViNTRjXHViZDgwXHVkMTMwICRLJFx1Yzc3YyBcdWI1NGNcdWFlNGNcdWM5YzAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM4MTVcdWM4MTAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMTggJE4kXHVhY2ZjIFx1YzgxNVx1YzIxOCAkSyRcdWFjMDAgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZXEgSyBcXGxlcSBOIFxcbGVxIDMwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjQ1MFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgJChOLTEpJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzA0XHVjMTIwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKGkrMSkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkQV9pLEJfaSxDX2kkXHVhYzAwIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGVxIGkgJmx0O04pJC4gXHVjNzc0XHViMjk0ICRBX2kkXHViYzg4IFx1YzgxNVx1YzgxMFx1YWNmYyAkQl9pJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YWMwMFx1YzkxMVx1Y2U1OCAkQ19pJFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTY4XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gJCgxIFxcbGVxIEFfaSxCX2ksQ19pIFxcbGVxIE4pJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWIyZjVcdWM3NDQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODhcdWM5ZjggXHViYWE4XHVjNzg0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0ICQoMSBcXGxlcSBpIFxcbGVxIE4pJC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDU1OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlc3QgTWVldGluZyBQbGFjZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgdHJlZSB3aXRoICROJCB2ZXJ0aWNlcyBpcyBnaXZlbi4gVmVydGljZXMgYXJlIG51bWJlcmVkIHNlcXVlbnRpYWxseSBmcm9tICQxJCB0byAkTiQuIFRoZSAkaSQtdGggZWRnZSBjb25uZWN0cyB2ZXJ0aWNlcyAkQV9pJCBhbmQgJEJfaSQsIGFuZCBoYXMgd2VpZ2h0ICRDX2kkLCBmb3IgJDEgXFxsZXEgaSBcXGxlcSBOIC0gMSQuPFwvcD5cclxuXHJcbjxwPlRoZSA8ZW0+dGVsZXBvcnQgZGlzdGFuY2U8XC9lbT4gYmV0d2VlbiB0d28gdmVydGljZXMgb2YgdGhlIHRyZWUgaXMgdGhlIG1heGltdW0gd2VpZ2h0IG9mIHRoZSBlZGdlIG9uIHRoZSBzaG9ydGVzdCBwYXRoIGNvbm5lY3RpbmcgdGhlbS4gVGhlIHRlbGVwb3J0IGRpc3RhbmNlIGJldHdlZW4gYSB2ZXJ0ZXggYW5kIGl0c2VsZiBpcyBkZWZpbmVkIGFzICQwJC48XC9wPlxyXG5cclxuPHA+UGVvcGxlIGxpdmluZyBvbiB0aGUgdHJlZSB3YW50IHRvIGhvbGQgJE4kIG1lZXRpbmdzLiBUaGUgJGkkLXRoIG1lZXRpbmcgaXMgYXR0ZW5kZWQgYnkgcGVvcGxlIGxpdmluZyBpbiB0aGUgdmVydGljZXMgbnVtYmVyZWQgZnJvbSAkMSQgdG8gJGkkLiBUaGlzIHllYXIsIGJlY2F1c2Ugb2YgdGhlIHNwcmVhZCBvZiBjb3JvbmF2aXJ1cywgdGhlIG1lZXRpbmcgcGFydGljaXBhbnRzIHdpbGwgYXJyaXZlIGF0ICRYJCBzZWxlY3RlZCBsb2NhdGlvbnMsIGFuZCB0aGVuIGNvbm5lY3QgdmlhIEludGVybmV0IGZyb20gdGhlc2UgbG9jYXRpb25zLjxcL3A+XHJcblxyXG48cD5Nb3JlIGZvcm1hbGx5LCBmb3IgZWFjaCBtZWV0aW5nLCB3ZSB3aWxsIGNob29zZSAkWCQgcGFpcndpc2UgZGlzdGluY3QgdmVydGljZXMgJHZfMSQsICR2XzIkLCAkXFxsZG90cyQsICR2X1gkLiBPbmNlIHRoZSB2ZXJ0aWNlcyBhcmUgZGV0ZXJtaW5lZCwgZWFjaCBwZXJzb24gd2lsbCBtb3ZlIHRvIG9uZSBvZiB0aGUgdmVydGljZXMgJHZfMSQsICRcXGxkb3RzJCwgJHZfWCQgd2l0aCB0aGUgbWluaW11bSB0ZWxlcG9ydCBkaXN0YW5jZSB0byBpdC4gTGV0IHVzIGRlZmluZSB0aGUgPGVtPm1lZXRpbmcgY29zdDxcL2VtPiBmb3IgdGhlIGdpdmVuICRYJCBhbmQgJGkkIGFzIHRoZSBtYXhpbXVtIG9mIHRlbGVwb3J0IGRpc3RhbmNlcyBmb3IgbWVldGluZyBwYXJ0aWNpcGFudHMuIFdlIHdpbGwgc2VsZWN0IHRoZSB2ZXJ0aWNlcyAkdl8xJCwgJFxcbGRvdHMkLCAkdl9YJCBpbiBzdWNoIGEgd2F5IHRoYXQgdGhlIG1lZXRpbmcgY29zdCBpcyBtaW5pbWFsIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5UaGUgdmFsdWUgb2YgJFgkIGRlcGVuZHMgb24gdGhlIGNvcm9uYXZpcnVzIHNpdHVhdGlvbiwgYW5kIG1heSB2YXJ5IGZyb20gJDEkIHRvICRLJC4gVG8gcHJlcGFyZSBmb3IgdGhlIG1lZXRpbmcgaW4gYWR2YW5jZSwgd3JpdGUgYSBwcm9ncmFtIHRoYXQsIGZvciBlYWNoIG9mIHRoZSAkTiQgbWVldGluZ3MsIGZpbmRzIHRoZSBzdW0gb2YgdGhlIG1lZXRpbmcgY29zdHMgZm9yIGFsbCBwb3NzaWJsZSB2YWx1ZXMgb2YgJFgkIGZyb20gJDEkIHRvICRLJCwgaW5jbHVzaXZlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzICROJCBhbmQgJEskOiB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGFuZCB0aGUgdXBwZXIgbGltaXQgZm9yICRYJCwgcmVzcGVjdGl2ZWx5ICgkMSBcXGxlcSBLIFxcbGVxIE4gXFxsZXEgMyBcXGNkb3QgMTBeNSQpLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nICROIC0gMSQgbGluZXMgZGVzY3JpYmUgdGhlIHRyZWUuIEVhY2ggb2YgdGhlc2UgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMsICRBX2kkLCAkQl9pJCwgYW5kICRDX2kkLCB0ZWxsaW5nIHRoYXQgdGhlcmUgaXMgYW4gZWRnZSBiZXR3ZWVuIHZlcnRpY2VzICRBX2kkIGFuZCAkQl9pJCB3aXRoIHdlaWdodCAkQ19pJCAoJDEgXFxsZXEgQV9pLCBCX2ksIENfaSBcXGxlcSBOJCkuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgcmVzdWx0aW5nIGdyYXBoIGlzIGEgdHJlZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCAkTiQgbGluZXMuIE9uIGxpbmUgJGkkLCBwcmludCB0aGUgc3VtIG9mIG1lZXRpbmcgY29zdHMgb2YgJGkkLXRoIG1lZXRpbmcgZm9yIGFsbCAkWCQgZnJvbSAkMSQgdG8gJEskLCBpbmNsdXNpdmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==