문제
$N$개의 정점으로 이루어진 트리(사이클이 없는 무방향 연결 그래프)가 있다. 정점은 1ドル$번부터 $N$번까지 번호가 매겨져 있고, 간선은 1ドル$번부터 $(N-1)$번까지 번호가 매겨져 있다.
아래의 쿼리를 수행하는 프로그램을 작성하시오.
- $u$ $v$: 정점 $x$(1ドル\le x\le N$)에 대해, $\operatorname{dist}(x,u)\times\operatorname{dist}(x,v)$의 최댓값을 출력한다. (1ドル\le u,v\le N$)
이때 $\operatorname{dist}(x,y)$는 정점 $x$에서 정점 $y$로 가는 최단 경로 상의 간선 개수로 정의한다. 트리의 모든 정점 $x$에 대해 $\operatorname{dist}(x,x) =0$이다.
출력
$Q$개의 줄에 쿼리의 답을 순서대로 출력한다.
W3sicHJvYmxlbV9pZCI6IjM0MDYyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiRGlzdGFuY2UgTXVsdGlwbGljYXRpb24gTWF4aW1pemF0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD4kTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQyYjhcdWI5YWMoXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0IFx1YzVjNlx1YjI5NCBcdWJiMzRcdWJjMjlcdWQ1YTUgXHVjNWYwXHVhY2IwIFx1YWRmOFx1Yjc5OFx1ZDUwNClcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM4MTVcdWM4MTBcdWM3NDAgJDEkXHViYzg4XHViZDgwXHVkMTMwICROJFx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhYzA0XHVjMTIwXHVjNzQwICQxJFx1YmM4OFx1YmQ4MFx1ZDEzMCAkKE4tMSkkXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OThcdWM3NTggXHVjZmZjXHViOWFjXHViOTdjIFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiR1JCAkdiQ6IFx1YzgxNVx1YzgxMCAkeCQoJDFcXGxlIHhcXGxlIE4kKVx1YzVkMCBcdWIzMDBcdWQ1NzQsICRcXG9wZXJhdG9ybmFtZXtkaXN0fSh4LHUpXFx0aW1lc1xcb3BlcmF0b3JuYW1le2Rpc3R9KHgsdikkXHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuICgkMVxcbGUgdSx2XFxsZSBOJCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMgJFxcb3BlcmF0b3JuYW1le2Rpc3R9KHgseSkkXHViMjk0IFx1YzgxNVx1YzgxMCAkeCRcdWM1ZDBcdWMxMWMgXHVjODE1XHVjODEwICR5JFx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1YyBcdWMwYzFcdWM3NTggXHVhYzA0XHVjMTIwIFx1YWMxY1x1YzIxOFx1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQuIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwICR4JFx1YzVkMCBcdWIzMDBcdWQ1NzQgJFxcb3BlcmF0b3JuYW1le2Rpc3R9KHgseCkgPTAkXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQyYjhcdWI5YWNcdWM3NTggXHVjODE1XHVjODEwIFx1YzIxOCAkTiRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDIgXFxsZSBOIFxcbGUgMzAwXFwsMDAwJCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICQoTi0xKSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODggXHVhYzA0XHVjMTIwXHVjNzc0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjODEwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDAgXHVjZmZjXHViOWFjXHVjNzU4IFx1YzIxOCAkUSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDIgXFxsZSBRIFxcbGUgMzAwXFwsMDAwJCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCAkUSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjZmZjXHViOWFjXHVjNzU4IFx1YjJmNVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM0MDYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGlzdGFuY2UgTXVsdGlwbGljYXRpb24gTWF4aW1pemF0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIHRyZWUgKGEgY29ubmVjdGVkIHVuZGlyZWN0ZWQgZ3JhcGggd2l0aCBubyBjeWNsZXMpIGNvbnNpc3Rpbmcgb2YgJE4kIHZlcnRpY2VzLiBUaGUgdmVydGljZXMgYXJlIG51bWJlcmVkIGZyb20gJDEkIHRvICROJCwgYW5kIHRoZSBlZGdlcyBhcmUgbnVtYmVyZWQgZnJvbSAkMSQgdG8gJChOLTEpJC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgcGVyZm9ybXMgdGhlIGZvbGxvd2luZyBxdWVyeS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kdSQgJHYkOiBGb3IgdmVydGV4ICR4JCAoJDFcXGxlIHhcXGxlIE4kKSwgcHJpbnQgdGhlIG1heGltdW0gdmFsdWUgb2YgJFxcb3BlcmF0b3JuYW1le2Rpc3R9KHgsdSlcXHRpbWVzXFxvcGVyYXRvcm5hbWV7ZGlzdH0oeCx2KSQuICgkMVxcbGUgdSx2XFxsZSBOJCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5IZXJlLCAkXFxvcGVyYXRvcm5hbWV7ZGlzdH0oeCx5KSQgaXMgZGVmaW5lZCBhcyB0aGUgbnVtYmVyIG9mIGVkZ2VzIG9uIHRoZSBzaG9ydGVzdCBwYXRoIGZyb20gdmVydGV4ICR4JCB0byB2ZXJ0ZXggJHkkLiBGb3IgYW55IHZlcnRleCAkeCQsICRcXG9wZXJhdG9ybmFtZXtkaXN0fSh4LHgpID0wJC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zICROJCwgZGVub3RpbmcgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBvZiB0aGUgdHJlZS4gKCQyIFxcbGUgTiBcXGxlIDMwMFxcLDAwMCQpPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgJChOLTEpJCBsaW5lcyBjb250YWluIHRoZSBpbmZvcm1hdGlvbiBvZiB0aGUgdHJlZS4gVGhlICRpJC10aCBvZiB0aGVtIGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgZGVub3RpbmcgdGhlIHR3byB2ZXJ0aWNlcyBjb25uZWN0ZWQgYnkgZWRnZSAkaSQuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgJFEkLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHF1ZXJpZXMuICgkMiBcXGxlIFEgXFxsZSAzMDBcXCwwMDAkKTxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJFEkIGxpbmVzIGNvbnRhaW5zIHRoZSBpbmZvcm1hdGlvbiBmb3IgZWFjaCBxdWVyeSBpbiB0aGUgc2FtZSBmb3JtYXQgYXMgd3JpdHRlbiBpbiB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgJFEkIGxpbmVzIGNvbnRhaW5pbmcgdGhlIGFuc3dlciB0byBlYWNoIHF1ZXJ5LCBvbmUgcGVyIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==