문제
$N$개의 도시와 $N-1$개의 도로로 이루어진 국가가 있다. 도시에는 1ドル$부터 $N$까지의 번호가 붙어 있고, 도로에도 1ドル$부터 $N-1$의 번호가 붙어 있다. $i$번 도로는 $A_i$번 도시와 $B_i$번 도시를 양방향으로 연결하고, 이동 시에는 $W_i$의 비용이 든다. 임의의 두 도시를 고르더라도 둘 사이를 하나 이상의 도로를 사용하여 왕복할 수 있음이 보장된다.
두 도시 사이의 거리를 한 도시에서 출발하여 하나 이상의 도로를 거쳐 다른 도시로 갈 때 필요한 최소 비용으로 정의하자.
당신은 도로 회사의 사장으로, 명절을 맞아 할인 행사를 진행하려고 한다. 할인 행사를 위한 총 $Q$개의 계획이 있다. $i$번째 계획에서는 $X_i$번 도시에서 출발하여 $Y_i$번 도시로 가는 최단 경로에 속하는 모든 도로들에 할인을 적용하여 비용을 0으로 만들 것이다. 각 할인 행사 계획에 대해, 두 도시 사이 거리의 최댓값을 출력하라.
출력
총 $Q$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번째 계획에 대한 답을 출력해야 한다.
제한
2ドル\le N\le 100,円 000$
1ドル\le A_i,B_i\le N$ (1ドル\le i\le N-1$)
$A_i\neq B_i$ (1ドル\le i\le N-1$)
1ドル\le W_i\le 10^9$ (1ドル\le i\le N-1$)
입력으로 주어지는 나라의 구조는 올바른 트리를 이룬다.
1ドル\le Q\le 100,円 000$
1ドル\le X_i,Y_i\le N$ (1ドル\le i\le Q$)
$X_i\neq Y_i$ (1ドル\le i\le Q$)
서브태스크 번호 배점 제한 1 10 $N, Q \le 2,000円$
2 24 $X_i=1$ (1ドル \le i \le Q$)
3 27 $Q=N-1$; $X_i = A_i$; $Y_i = B_i$ (1ドル \le i \le N-1$)
4 39 추가적인 제약 조건이 없다.
예제 출력 3
복사
13
13
16
16
13
16
15
예제 출력 4
복사
12
11
11
12
7
11
W3sicHJvYmxlbV9pZCI6IjMxODE4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiRGlzY291bnQgRXZlbnQiLCJkZXNjcmlwdGlvbiI6IjxwPiROJFx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWM2NDAgJE4tMSRcdWFjMWNcdWM3NTggXHViM2M0XHViODVjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFkNmRcdWFjMDBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWIzYzRcdWMyZGNcdWM1ZDBcdWIyOTQgJDEkXHViZDgwXHVkMTMwICROJFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHViM2M0XHViODVjXHVjNWQwXHViM2M0ICQxJFx1YmQ4MFx1ZDEzMCAkTi0xJFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNWI0IFx1Yzc4OFx1YjJlNC4gJGkkXHViYzg4IFx1YjNjNFx1Yjg1Y1x1YjI5NCAkQV9pJFx1YmM4OCBcdWIzYzRcdWMyZGNcdWM2NDAgJEJfaSRcdWJjODggXHViM2M0XHVjMmRjXHViOTdjIFx1YzU5MVx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjZTAsIFx1Yzc3NFx1YjNkOSBcdWMyZGNcdWM1ZDBcdWIyOTQgJFdfaSRcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzc0IFx1YjRlMFx1YjJlNC4gXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWI5N2MgXHVhY2UwXHViOTc0XHViMzU0XHViNzdjXHViM2M0IFx1YjQ1OCBcdWMwYWNcdWM3NzRcdWI5N2MgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTU4XHVjNWVjIFx1YzY1NVx1YmNmNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIFx1ZDU1YyBcdWIzYzRcdWMyZGNcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHVjNWVjIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHViM2M0XHViODVjXHViOTdjIFx1YWM3MFx1Y2NkMCBcdWIyZTRcdWI5NzggXHViM2M0XHVjMmRjXHViODVjIFx1YWMwOCBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHViM2M0XHViODVjIFx1ZDY4Y1x1YzBhY1x1Yzc1OCBcdWMwYWNcdWM3YTVcdWM3M2NcdWI4NWMsIFx1YmE4NVx1YzgwOFx1Yzc0NCBcdWI5ZGVcdWM1NDQgXHVkNTYwXHVjNzc4IFx1ZDU4OVx1YzBhY1x1Yjk3YyBcdWM5YzRcdWQ1ODlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ1NjBcdWM3NzggXHVkNTg5XHVjMGFjXHViOTdjIFx1YzcwNFx1ZDU1YyBcdWNkMWQgJFEkXHVhYzFjXHVjNzU4IFx1YWNjNFx1ZDY4ZFx1Yzc3NCBcdWM3ODhcdWIyZTQuICRpJFx1YmM4OFx1YzlmOCBcdWFjYzRcdWQ2OGRcdWM1ZDBcdWMxMWNcdWIyOTQgJFhfaSRcdWJjODggXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1OFx1YzVlYyAkWV9pJFx1YmM4OCBcdWIzYzRcdWMyZGNcdWI4NWMgXHVhYzAwXHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIzYzRcdWI4NWNcdWI0ZTRcdWM1ZDAgXHVkNTYwXHVjNzc4XHVjNzQ0IFx1YzgwMVx1YzZhOVx1ZDU1OFx1YzVlYyBcdWJlNDRcdWM2YTlcdWM3NDQgMFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFjMDEgXHVkNTYwXHVjNzc4IFx1ZDU4OVx1YzBhYyBcdWFjYzRcdWQ2OGRcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWI0NTAgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NCBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJE4tMSRcdWFjMWNcdWM3NTggXHVjOTA0IFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggJEFfaSQsICRCX2kkLCAkV19pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNGU0XHVjNzQwICRpJFx1YmM4OFx1YzlmOCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM3NzRcdWIzZDkgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWFjYzRcdWQ2OGRcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggJFEkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDQgXHVjOTExICRpJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCAkWF9pJFx1YzY0MCAkWV9pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNGU0XHVjNzQwICRpJFx1YmM4OFx1YzlmOCBcdWFjYzRcdWQ2OGRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2QxZCAkUSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICRpJFx1YmM4OFx1YzlmOCBcdWFjYzRcdWQ2OGRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMlxcbGUgTlxcbGUgMTAwXFwsIDAwMCQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlIEFfaSxCX2lcXGxlIE4kICgkMVxcbGUgaVxcbGUgTi0xJCk8XC9saT5cclxuXHQ8bGk+JEFfaVxcbmVxIEJfaSQgKCQxXFxsZSBpXFxsZSBOLTEkKTxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgV19pXFxsZSAxMF45JCAoJDFcXGxlIGlcXGxlIE4tMSQpPFwvbGk+XHJcblx0PGxpPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViMDk4XHViNzdjXHVjNzU4IFx1YWQ2Y1x1Yzg3MFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVkMmI4XHViOWFjXHViOTdjIFx1Yzc3NFx1YjhlY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+JDFcXGxlIFFcXGxlIDEwMFxcLCAwMDAkPFwvbGk+XHJcblx0PGxpPiQxXFxsZSBYX2ksWV9pXFxsZSBOJCAoJDFcXGxlIGlcXGxlIFEkKTxcL2xpPlxyXG5cdDxsaT4kWF9pXFxuZXEgWV9pJCAoJDFcXGxlIGlcXGxlIFEkKTxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiwgUSBcXGxlIDJcXCwwMDAkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kWF9pPTEkICgkMSBcXGxlIGkgXFxsZSBRJCk8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPiRRPU4tMSQ7ICRYX2kgPSBBX2kkOyAkWV9pID0gQl9pJCAoJDEgXFxsZSBpIFxcbGUgTi0xJCk8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPlx1Y2Q5NFx1YWMwMFx1YzgwMVx1Yzc3OCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0XHVjNzc0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTgxOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRpc2NvdW50IEV2ZW50IiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIGNvdW50cnkgd2l0aCAkTiQgY2l0aWVzIGFuZCAkTi0xJCByb2Fkcy4gRWFjaCBjaXR5IGlzIGxhYmVsZWQgd2l0aCBpbnRlZ2VycyBmcm9tICQxJCB0byAkTiQsIGFuZCBlYWNoIHJvYWQgaXMgbGFiZWxlZCB3aXRoIGludGVnZXJzIGZyb20gJDEkIHRvICROLTEkLiBUaGUgJGkkLXRoIHJvYWQgY29ubmVjdHMgY2l0aWVzICRBX2kkIGFuZCAkQl9pJCBiaWRpcmVjdGlvbmFsbHksIGFuZCBoYXMgdHJhdmVsIGNvc3RzICRXX2kkLiBZb3UgY2FuIHRyYXZlbCBhbG9uZyBhbnkgcGFpciBvZiBjaXRpZXMgdXNpbmcgdGhlIHJvYWRzLjxcL3A+XHJcblxyXG48cD5UaGUgZGlzdGFuY2UgYmV0d2VlbiB0d28gY2l0aWVzIGlzIGRlZmluZWQgYXMgdGhlIG1pbmltdW0gY29zdCBvZiBtb3ZpbmcgZnJvbSBvbmUgY2l0eSB0byBhbm90aGVyLjxcL3A+XHJcblxyXG48cD5BcyB0aGUgcHJlc2lkZW50IG9mIGEgcm9hZCBjb21wYW55LCB5b3UgYXJlIHBsYW5uaW5nIGEgZGlzY291bnQgZXZlbnQgZm9yIHRoZSBob2xpZGF5cy4gVGhlcmUgYXJlIGEgdG90YWwgb2YgJFEkIHBsYW5zIGZvciB0aGUgZGlzY291bnQgZXZlbnQuIEluIHRoZSAkaSQtdGggcGxhbiwgdGhlIGRpc2NvdW50IGlzIGFwcGxpZWQgdG8gYWxsIHJvYWRzIGluIHRoZSBzaG9ydGVzdCBwYXRoIGJldHdlZW4gY2l0aWVzICRYX2kkIGFuZCAkWV9pJCwgYW5kIHRoZSB0cmF2ZWwgY29zdHMgb2YgdGhlIHJvYWQgYmVjb21lIHplcm8uIEZvciBlYWNoIGRpc2NvdW50IGV2ZW50IHBsYW4sIGNvbXB1dGUgdGhlIG1heGltdW0gdmFsdWUgb2YgdGhlIGRpc3RhbmNlIGJldHdlZW4gYW55IHR3byBjaXRpZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICROJCAmbWRhc2g7IHRoZSBudW1iZXIgb2YgY2l0aWVzLjxcL3A+XHJcblxyXG48cD5UaGUgJGkkLXRoIG9mIHRoZSBuZXh0ICROLTEkIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzICRBX2kkLCAkQl9pJCwgYW5kICRXX2kkIHNlcGFyYXRlZCBieSBhIHNwYWNlICZtZGFzaDsgdGhlIGNpdGllcyB0aGUgJGkkLXRoIHJvYWQgY29ubmVjdHMgYW5kIHRoZSByb2FkJnJzcXVvO3MgdHJhdmVsIGNvc3QuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciAkUSQgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHBsYW5zLjxcL3A+XHJcblxyXG48cD5UaGUgJGkkLXRoIG9mIHRoZSBuZXh0ICRRJCBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgJFhfaSQgYW5kICRZX2kkIHNlcGFyYXRlZCBieSBhIHNwYWNlLCBkZXNjcmliaW5nIHRoZSAkaSQtdGggcGxhbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgYW5zd2VyIGFsb25nICRRJCBsaW5lcy4gSW4gdGhlICRpJC10aCBsaW5lLCB5b3Ugc2hvdWxkIHByaW50IHRoZSBhbnN3ZXIgZm9yIHRoZSAkaSQtdGggcXVlcnkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMlxcbGUgTlxcbGUgMTAwXFwsIDAwMCQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlIEFfaSxCX2lcXGxlIE4kICgkMVxcbGUgaVxcbGUgTi0xJCk8XC9saT5cclxuXHQ8bGk+JEFfaVxcbmVxIEJfaSQgKCQxXFxsZSBpXFxsZSBOLTEkKTxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgV19pXFxsZSAxMF45JCAoJDFcXGxlIGlcXGxlIE4tMSQpPFwvbGk+XHJcblx0PGxpPkl0IGlzIHBvc3NpYmxlIHRvIHRyYXZlbCBhbG9uZyBhbnkgcGFpciBvZiBjaXRpZXMgdXNpbmcgdGhlIHJvYWRzLjxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgUVxcbGUgMTAwXFwsIDAwMCQ8XC9saT5cclxuXHQ8bGk+JDFcXGxlIFhfaSxZX2lcXGxlIE4kICgkMVxcbGUgaVxcbGUgUSQpPFwvbGk+XHJcblx0PGxpPiRYX2lcXG5lcSBZX2kkICgkMVxcbGUgaVxcbGUgUSQpPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROLCBRIFxcbGUgMlxcLDAwMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRYX2k9MSQgKCQxIFxcbGUgaSBcXGxlIFEkKTxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+JFE9Ti0xJDsgJFhfaSA9IEFfaSQ7ICRZX2kgPSBCX2kkICgkMSBcXGxlIGkgXFxsZSBOLTEkKTxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50cy48XC9wPlxyXG4ifV0=