시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB88281724.286%

문제

N개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, i번 정점에는 정수 Ai가 저장되어 있다. 처음 상태에서 Ai=0이다. (1 ≤ iN

당신은 다음과 같은 쿼리를 총 Q번 수행해야 한다.

  • 1 u v: 트리의 루트를 정점 u라 하였을 때, 정점 v를 루트로 하는 서브트리의 모든 정점 iAi에 1을 더한다.
  • 2 u v: 정점 u에서 정점 v로 가는 유일한 경로에 있는 모든 정점 iAi에 1을 더한다.
  • 3 v: $\sum_{i = 1}^{N} A_i \times dist(v, i)$를 출력한다. $dist(x, y)$는 정점 x에서 정점 y로 가는 경로에 있는 간선의 수를 의미한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

다음 N-1개 줄에 트리의 간선이 주어진다. 각 줄에는 공백으로 구분된 두 수 uv가 주어지고, uv를 연결하는 간선이 있다는 것을 의미한다. (1 ≤ u, vN)

다음 줄에는 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)  

다음 Q개의 줄에는 한 줄에 하나씩 다음과 같은 형식 중 하나로 쿼리가 주어진다.

  • 1 u v (1 ≤ u, vN)
  • 2 u v (1 ≤ u, vN)
  • 3 v (1 ≤ vN)

3번 쿼리는 한 번 이상 주어진다.

출력

각각의 3번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

5
4 2
2 5
1 5
1 3
5
2 2 4
3 4
2 1 5
2 5 5
3 2

예제 출력 1

1
5
W3sicHJvYmxlbV9pZCI6IjIwMTQ4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI4XHViOWFjXHVjNjQwIFx1Y2ZmY1x1YjlhYyAxOCIsImRlc2NyaXB0aW9uIjoiPHA+PGVtPk48XC9lbT5cdWFjMWNcdWM3NTggXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM4MTVcdWM4MTBcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCA8ZW0+TjxcL2VtPlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YWNlMCwgPGVtPmk8XC9lbT5cdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCA8ZW0+QTxzdWI+aTxcL3N1Yj48XC9lbT5cdWFjMDAgXHVjODAwXHVjN2E1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjYzk4XHVjNzRjIFx1YzBjMVx1ZDBkY1x1YzVkMFx1YzExYyZuYnNwOzxlbT5BPHN1Yj5pPFwvc3ViPjxcL2VtPj0wXHVjNzc0XHViMmU0LiAoMSAmbGU7IDxlbT5pPFwvZW0+ICZsZTsgPGVtPk48XC9lbT4pJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Y2ZmY1x1YjlhY1x1Yjk3YyBcdWNkMWQgPGVtPlE8XC9lbT5cdWJjODggXHVjMjE4XHVkNTg5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48Y29kZT4xIHUgdjxcL2NvZGU+OiBcdWQyYjhcdWI5YWNcdWM3NTggXHViOGU4XHVkMmI4XHViOTdjIFx1YzgxNVx1YzgxMCA8ZW0+dTxcL2VtPlx1Yjc3YyBcdWQ1NThcdWM2MDBcdWM3NDQgXHViNTRjLCBcdWM4MTVcdWM4MTAgPGVtPnY8XC9lbT5cdWI5N2MgXHViOGU4XHVkMmI4XHViODVjIFx1ZDU1OFx1YjI5NCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWM3NTggXHViYWE4XHViNGUwIFx1YzgxNVx1YzgxMCA8ZW0+aTxcL2VtPlx1Yzc1OCA8ZW0+QTxzdWI+aTxcL3N1Yj48XC9lbT5cdWM1ZDAgMVx1Yzc0NCBcdWIzNTRcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjxjb2RlPjIgdSB2PFwvY29kZT46IFx1YzgxNVx1YzgxMCA8ZW0+dTxcL2VtPlx1YzVkMFx1YzExYyBcdWM4MTVcdWM4MTAgPGVtPnY8XC9lbT5cdWI4NWMgXHVhYzAwXHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWFjYmRcdWI4NWNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTAgPGVtPmk8XC9lbT5cdWM3NTggPGVtPkE8c3ViPmk8XC9zdWI+PFwvZW0+XHVjNWQwIDFcdWM3NDQgXHViMzU0XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT48Y29kZT4zIHY8XC9jb2RlPjogJFxcc3VtX3tpJm5ic3A7PSAxfV57Tn0gQV9pJm5ic3A7XFx0aW1lcyBkaXN0KHYsIGkpJFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuICRkaXN0KHgsIHkpJFx1YjI5NCBcdWM4MTVcdWM4MTAmbmJzcDs8ZW0+eDxcL2VtPlx1YzVkMFx1YzExYyBcdWM4MTVcdWM4MTAgPGVtPnk8XC9lbT5cdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgPGVtPk48XC9lbT5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IDxlbT5OPFwvZW0+ICZsZTsmbmJzcDsyMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgPGVtPk48XC9lbT4tMVx1YWMxYyBcdWM5MDRcdWM1ZDAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQmbmJzcDtcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjIFx1YjQ1MCBcdWMyMTggPGVtPnU8XC9lbT5cdWM2NDAgPGVtPnY8XC9lbT5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCA8ZW0+dTxcL2VtPlx1YzY0MCA8ZW0+djxcL2VtPlx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiAoMSAmbGU7IDxlbT51PFwvZW0+LCA8ZW0+djxcL2VtPiAmbGU7IDxlbT5OPFwvZW0+KTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMTggPGVtPlE8XC9lbT5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IDxlbT5RPFwvZW0+ICZsZTsgMjAwLDAwMCkmbmJzcDsmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIDxlbT5RPFwvZW0+XHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZCBcdWM5MTEgXHVkNTU4XHViMDk4XHViODVjIFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PGNvZGU+MSB1IHY8XC9jb2RlPiZuYnNwOygxICZsZTsgPGVtPnU8XC9lbT4sIDxlbT52PFwvZW0+ICZsZTsgPGVtPk48XC9lbT4pPFwvbGk+XHJcblx0PGxpPjxjb2RlPjIgdSB2PFwvY29kZT4gKDEgJmxlOyA8ZW0+dTxcL2VtPiwgPGVtPnY8XC9lbT4gJmxlOyA8ZW0+TjxcL2VtPik8XC9saT5cclxuXHQ8bGk+PGNvZGU+MyB2PFwvY29kZT4gKDEgJmxlOyA8ZW0+djxcL2VtPiAmbGU7IDxlbT5OPFwvZW0+KTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjNcdWJjODggXHVjZmZjXHViOWFjXHViMjk0IFx1ZDU1YyBcdWJjODggXHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggM1x1YmM4OCBcdWNmZmNcdWI5YWNcdWM3NTggXHVhY2IwXHVhY2ZjXHViOTdjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjAxNDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbm90aGVyIFRyZWUgUXVlcmllcyBQcm9ibGVtIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgaGF2ZSBhIHRyZWUgb2YgJE4kIHZlcnRpY2VzLiBWZXJ0aWNlcyBhcmUgZW51bWVyYXRlZCBieSBzZXF1ZW50aWFsIGludGVnZXJzIGZyb20gMSB0byAkTiQsIGFuZCB0aGUgJGkkLXRoIHZlcnRleCBjb250YWlucyB0aGUgdmFyaWFibGUgJEFfaSQuIEluaXRpYWxseSAkQV9pJCA9IDAgKCQxIFxcbGUgaSBcXGxlIE4kKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgdG8gcHJvY2VzcyAkUSQgcXVlcmllcy4gRWFjaCBxdWVyeSBpcyBvbmUgb2YgdGhlIGZvbGxvd2luZzo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mcXVvdDs8Y29kZT4xICR1JCAkdiQ8XC9jb2RlPiZxdW90OzogUm9vdCB0aGUgdHJlZSBhdCB2ZXJ0ZXggJHUkLCBjb25zaWRlciB0aGUgc3VidHJlZSBvZiB2ZXJ0ZXggJHYkLCBhbmQgZm9yIGVhY2ggdmVydGV4ICRpJCBpbiB0aGUgc3VidHJlZSBvZiAkdiQsIGluY3JlYXNlICRBX2kkIGJ5IG9uZS48XC9saT5cclxuXHQ8bGk+JnF1b3Q7PGNvZGU+MiAkdSQgJHYkPFwvY29kZT4mcXVvdDs6IEZvciBlYWNoIHZlcnRleCAkaSQgaW4gdGhlIHVuaXF1ZSBzaW1wbGUgcGF0aCBmcm9tICR1JCB0byAkdiQsIGluY3JlYXNlICRBX2kkIGJ5IG9uZS48XC9saT5cclxuXHQ8bGk+JnF1b3Q7PGNvZGU+MyAkdiQ8XC9jb2RlPiZxdW90OzogUHJpbnQgJFxcZGlzcGxheXN0eWxlIFxcc3VtXFxsaW1pdHNfe2k9MX1eTiBcXG1hdGhybXtkaXN0fSAodiwgaSkgXFxjZG90IEFfaSQsPFwvbGk+XHJcblx0PGxpPndoZXJlICRcXG1hdGhybXtkaXN0fSAoeCwgeSkkIGlzIHRoZSBudW1iZXIgb2YgZWRnZXMgaW4gdGhlIHBhdGggZnJvbSB2ZXJ0ZXggJHgkIHRvIHZlcnRleCAkeSQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgJE4kLCB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzICgkMSBcXGxlIE4gXFxsZSAyIFxcY2RvdCAxMF41JCkuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0ICROIC0gMSQgbGluZXMgY29udGFpbiB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIHRyZWUuIEVhY2ggc3VjaCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyAkdSQgYW5kICR2JCBzZXBhcmF0ZWQgYnkgYSBzcGFjZSwgbWVhbmluZyB0aGF0IHRoZXJlIGlzIGFuIGVkZ2UgY29ubmVjdGluZyAkdSQgYW5kICR2JCAoJDEgXFxsZSB1LCB2IFxcbGUgTiQpLiBJdCBpcyBndWFyYW50ZWVkIHRoYXQgdGhlIHJlc3VsdGluZyBncmFwaCBpcyBhIHRyZWUuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciAkUSQsIHRoZSBudW1iZXIgb2YgcXVlcmllcyAoJDEgXFxsZSBRIFxcbGUgMiBcXGNkb3QgMTBeNSQpLiAmbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgJFEkIGxpbmVzIGNvbnRhaW4gcXVlcmllcywgb25lIHBlciBsaW5lLiBFYWNoIHF1ZXJ5IGlzIGdpdmVuIGluIG9uZSBvZiB0aGUgZm9ybWF0cyBkZXNjcmliZWQgYWJvdmUgKCQxIFxcbGUgdSwgdiBcXGxlIE4kKS4gWW91IG1heSBhc3N1bWUgdGhhdCB0aGVyZSBpcyBhdCBsZWFzdCBvbmUgcXVlcnkgb2YgdHlwZSAmcXVvdDs8Y29kZT4zPFwvY29kZT4mcXVvdDsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcXVlcnkgb2YgdHlwZSAmcXVvdDs8Y29kZT4zPFwvY29kZT4mcXVvdDssIHByaW50IHRoZSByZXN1bHQgb24gYSBzZXBhcmF0ZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=