시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1024 MB 48 16 13 50.000%

문제

$N$개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 $N$번까지 번호가 매겨져 있고, 1번 정점은 루트이다. 각 정점 $i$에는 정수 $A[i]$가 저장되어 있다. 가장 처음에 $A[i]$는 0이다.

다음과 같은 쿼리를 수행해야 한다.

  • 1 u: 정점 $u$를 루트로 하는 서브 트리의 모든 정점 $i$의 $A[i]$에 1을 더한다.
  • 2 u v: 정점 $u$에서 정점 $v$로 가는 유일한 최단 경로에 있는 모든 정점 $i$의 $A[i]$에 1을 더한다. $u$와 $v$는 같을 수도 있다.

각각의 쿼리를 수행한 후 $\sum_{y = 1}^{N} A[y] \times dist(x, y)$ 의 값을 가장 작게 만드는 정점 $x$를 출력한다. $dist(x, y)$ 는 $x$에서 $y$로 가는 경로에 존재하는 간선의 개수와 같다. 가능한 정점 x가 여러가지면, 루트에서 거리가 가장 가까운 정점을 출력한다. 그러한 정점은 항상 유일하다는 것을 증명할 수 있다.

입력

첫째 줄에 $N$이 주어진다. ($2 \le N \le 100\,000$)

다음 $N-1$개의 줄에는 트리의 간선이 주어진다. 각 줄은 공백으로 구분된 두 정수 $u$와 $v$가 주어지고, 정점 $u$와 정점 $v$를 연결하는 간선을 의미한다. ($1 \le u, v \le N, u \neq v$)

다음 줄에는 수행해야 하는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 100\,000$).

다음 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어지며, 쿼리는 다음과 같은 형식이다.

  • 1 u ($1 \le u \le N$)
  • 2 u v ($1 \le u, v \le N$)

출력

쿼리를 수행한 후 출력해야 하는 값을 Q개의 줄에 순서대로 출력한다.

예제 입력 1

7
1 6
1 7
7 3
3 2
7 5
5 4
4
1 2
1 4
1 6
2 6 7

예제 출력 1

2
7
7
1
W3sicHJvYmxlbV9pZCI6IjIwMDMwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI4XHViOWFjXHVjNjQwIFx1Y2ZmY1x1YjlhYyAxNyIsImRlc2NyaXB0aW9uIjoiPHA+JE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkMmI4XHViOWFjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjODE1XHVjODEwXHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgJE4kXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHVhY2UwLCAxXHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWI4ZThcdWQyYjhcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWM4MTAgJGkkXHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCAkQVtpXSRcdWFjMDAgXHVjODAwXHVjN2E1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCAkQVtpXSRcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWNmZmNcdWI5YWNcdWI5N2MgXHVjMjE4XHVkNTg5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48Y29kZT4xIHU8XC9jb2RlPjogXHVjODE1XHVjODEwICR1JFx1Yjk3YyBcdWI4ZThcdWQyYjhcdWI4NWMgXHVkNTU4XHViMjk0IFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM3NTggXHViYWE4XHViNGUwIFx1YzgxNVx1YzgxMCAkaSRcdWM3NTggJEFbaV0kXHVjNWQwIDFcdWM3NDQgXHViMzU0XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT48Y29kZT4yIHUgdjxcL2NvZGU+OiBcdWM4MTVcdWM4MTAgJHUkXHVjNWQwXHVjMTFjIFx1YzgxNVx1YzgxMCAkdiRcdWI4NWMgXHVhYzAwXHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwICRpJFx1Yzc1OCAkQVtpXSRcdWM1ZDAgMVx1Yzc0NCBcdWIzNTRcdWQ1NWNcdWIyZTQuICR1JFx1YzY0MCAkdiRcdWIyOTQgXHVhYzE5XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1Y2ZmY1x1YjlhY1x1Yjk3YyBcdWMyMThcdWQ1ODlcdWQ1NWMgXHVkNmM0Jm5ic3A7JFxcc3VtX3t5ID0gMX1ee059IEFbeV0gXFx0aW1lcyBkaXN0KHgsIHkpJCBcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWFjOGMgXHViOWNjXHViNGRjXHViMjk0IFx1YzgxNVx1YzgxMCAkeCRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOyRkaXN0KHgsIHkpJCBcdWIyOTQgJHgkXHVjNWQwXHVjMTFjJm5ic3A7JHkkXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgXHVhYzE5XHViMmU0LiBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjODE1XHVjODEwIHhcdWFjMDAgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHViYTc0LCBcdWI4ZThcdWQyYjhcdWM1ZDBcdWMxMWMgXHVhYzcwXHViOWFjXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHVjODE1XHVjODEwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2VjXHVkNTVjIFx1YzgxNVx1YzgxMFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjNzIwXHVjNzdjXHVkNTU4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM5OWRcdWJhODVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoJDIgXFxsZSBOIFxcbGUgMTAwXFwsMDAwJCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICROLTEkXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjIFx1YjQ1MCBcdWM4MTVcdWMyMTggJHUkXHVjNjQwICR2JFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YzgxNVx1YzgxMCAkdSRcdWM2NDAgXHVjODE1XHVjODEwICR2JFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gKCQxIFxcbGUgdSwgdiBcXGxlIE4sIHUgXFxuZXEgdiQpPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVkNTg5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWNmZmNcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4ICRRJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgkMSBcXGxlIFEgXFxsZSAxMDBcXCwwMDAkKS48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICRRJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZmZjXHViOWFjXHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjZmZjXHViOWFjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPjEgdTxcL2NvZGU+Jm5ic3A7KCQxIFxcbGUgdSBcXGxlIE4kKTxcL2xpPlxyXG5cdDxsaT48Y29kZT4yIHUgdjxcL2NvZGU+Jm5ic3A7KCQxIFxcbGUgdSwgdiBcXGxlIE4kKTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZmZjXHViOWFjXHViOTdjIFx1YzIxOFx1ZDU4OVx1ZDU1YyBcdWQ2YzQgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjMTJcdWM3NDQgUVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMDAzMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlF1ZXJ5IE9uIEEgVHJlZSAxNyIsImRlc2NyaXB0aW9uIjoiPHA+T24gPGVtPkJhZWtqb29uIE9ubGluZSBKdWRnZTxcL2VtPiwgdGhlcmUgYXJlIGEgc2VyaWVzIG9mIHByb2JsZW1zIHJlbGF0ZWQgdG8gcHJvY2Vzc2luZyBxdWVyaWVzIG9uIGEgdHJlZS4gV2UgS0FJU1RpYW5zIGFyZSBwcm91ZCB0byBvZmZlciB0aGUgc2V2ZW50ZWVudGggZWRpdGlvbiBpbiB0aGlzIHNlcmllcy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiBhIHRyZWUgd2l0aCAkTiQgdmVydGljZXMuIEVhY2ggdmVydGV4IGlzIG51bWJlcmVkIGZyb20gMSB0byAkTiQuIFRoZSB0cmVlIGlzIHJvb3RlZCBhdCB2ZXJ0ZXggMS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+UGVvcGxlIGNhbiBsaXZlIGluIGVhY2ggdmVydGV4LiBMZXQgJEFbaV0kIGJlIHRoZSBudW1iZXIgb2YgcGVvcGxlIGxpdmluZyBpbiB2ZXJ0ZXggJGkkLiBJbml0aWFsbHksICRBW2ldID0gMCQgZm9yIGFsbCAkMSBcXGxlIGkgXFxsZSBOJC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgcHJvY2Vzc2VzIHRoZSAkUSQgZm9sbG93aW5nIHF1ZXJpZXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGNvZGU+MSB1PFwvY29kZT46Jm5ic3A7QWRkICQxJCB0byAkQVtpXSQgZm9yIGFsbCB2ZXJ0aWNlcyAkaSQgaW4gdGhlIHN1YnRyZWUgcm9vdGVkIGF0IHZlcnRleCAkdSQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPjxjb2RlPjIgdSB2PFwvY29kZT46Jm5ic3A7QWRkICQxJCB0byAkQVtpXSQgZm9yIGFsbCB2ZXJ0aWNlcyAkaSQgb24gdGhlIHVuaXF1ZSBzaG9ydGVzdCBwYXRoIGJldHdlZW4gdGhlIHR3byB2ZXJ0aWNlcyAkdSQgYW5kICR2JC4gTm90ZSB0aGF0ICR1JCBhbmQgJHYkIG1pZ2h0IGJlIGVxdWFsLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFmdGVyIGVhY2ggcXVlcnksIHByaW50IHRoZSB2ZXJ0ZXggJHgkIHRoYXQgbWluaW1pemVzIHRoZSBxdWFudGl0eSAkXFxzdW1fe3kgPSAxfV57Tn0gQVt5XSBcXHRpbWVzIGRpc3QoeCwgeSkkLCB3aGVyZSAkZGlzdCh4LCB5KSQgaXMgdGhlIG51bWJlciBvZiBlZGdlcyBvbiB0aGUgcGF0aCBiZXR3ZWVuICR4JCBhbmQgJHkkLiBJZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIHN1Y2ggdmVydGV4LCBwcmludCB0aGUgdmVydGV4IHdpdGggbWluaW11bSBkaXN0YW5jZSBmcm9tIHRoZSByb290ICh2ZXJ0ZXggMSkuJm5ic3A7SXQgY2FuIGJlIHByb3ZlbiB0aGF0IHN1Y2ggdmVydGV4IGlzIHVuaXF1ZS4gSW4gb3RoZXIgd29yZHMsIHdlIHNob3VsZCBmaW5kIGEgdmVydGV4IHRoYXQgbWluaW1pemVzIHRoZSB0b3RhbCBkaXN0YW5jZSBuZWVkZWQgZm9yIGV2ZXJ5b25lIHRvIGdhdGhlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBzaW5nbGUgaW50ZWdlciAkTiQgKCQyIFxcbGUgTiBcXGxlIDEwMFxcLDAwMCQpLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCAkTi0xJCBsaW5lcyBkZXNjcmliZSBhbGwgZWRnZXMgb2YgdGhlIHRyZWUuIEVhY2ggbGluZSBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICR1LCB2JCBkZW5vdGluZyB0aGF0IHRoZXJlIGlzIGFuIGVkZ2UgY29ubmVjdGluZyB2ZXJ0aWNlcyAkdSQgYW5kICR2JC4gKCQxIFxcbGUgdSwgdiBcXGxlIE4sIHUgXFxuZXEgdiQpPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgdGhlIHNpbmdsZSBpbnRlZ2VyICRRJCAoJDEgXFxsZSBRIFxcbGUgMTAwXFwsMDAwJCkuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0ICRRJCBsaW5lcyBjb250YWlucyBzZXZlcmFsIGludGVnZXJzIGluIG9uZSBvZiB0aGUgZm9sbG93aW5nIGZvcm1zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxjb2RlPjEgdTxcL2NvZGU+Jm5ic3A7KCQxIFxcbGUgdSBcXGxlIE4kKTxcL2xpPlxyXG5cdDxsaT48Y29kZT4yIHUgdjxcL2NvZGU+Jm5ic3A7KCQxIFxcbGUgdSwgdiBcXGxlIE4kKTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgJFEkIGxpbmVzLCBkZW5vdGluZyB0aGUgYW5zd2VyIGFmdGVyIGVhY2ggdXBkYXRlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

University > KAIST > 2020 KAIST 10th ICPC Mock Competition H번