시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 139 86 37 48.684%

문제

N개의 농장과 농장을 양방향으로 연결하는 N-1개의 도로가 있다. 임의의 두 농장 사이에는 하나의 경로만 존재한다. 농장은 1번부터 N번까지 번호가 매겨져 있다.

농장을 관리하는 재현이는 도로에 나무를 심기로 결정했다. 나무를 심는 과정은 쿼리로 이루어져 있으며, 쿼리는 총 2가지가 존재한다.

  • P u v: u번 농장과 v번 농장 사이의 경로에 존재하는 모든 도로에 나무를 하나씩 심는다.
  • Q u v: u번 농장과 v번 농장 사이의 경로에 존재하는 나무의 개수를 출력한다.

쿼리를 수행해보자.

입력

첫째 줄에 농장의 수 N과 쿼리의 수 M(1 ≤ N, M ≤ 100,000)이 주어진다.

둘째 줄부터 N-1개의 줄에는 도로가 연결하는 농장의 번호가 주어진다.

다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 쿼리는 한 개의 문자 w와 두 개의 정수 u, v로 이루어져 있고, 문제에서 설명한 형식이다.

출력

쿼리 Q가 주어질 때 마다, 나무의 개수를 출력한다.

예제 입력 1

4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4

예제 출력 1

2
1
2
W3sicHJvYmxlbV9pZCI6IjU5MTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxOGRcdWM3YTUgXHVhZDAwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5OXHVhYzFjXHVjNzU4IFx1YjE4ZFx1YzdhNVx1YWNmYyBcdWIxOGRcdWM3YTVcdWM3NDQgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBOLTFcdWFjMWNcdWM3NTggXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjQ1MCBcdWIxOGRcdWM3YTUgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWI5Y2MgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWIxOGRcdWM3YTVcdWM3NDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIxOGRcdWM3YTVcdWM3NDQgXHVhZDAwXHViOWFjXHVkNTU4XHViMjk0IFx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM1ZDAgXHViMDk4XHViYjM0XHViOTdjIFx1YzJlY1x1YWUzMFx1Yjg1YyBcdWFjYjBcdWM4MTVcdWQ1ODhcdWIyZTQuIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWMyZWNcdWIyOTQgXHVhY2ZjXHVjODE1XHVjNzQwIFx1Y2ZmY1x1YjlhY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWNmZmNcdWI5YWNcdWIyOTQgXHVjZDFkIDJcdWFjMDBcdWM5YzBcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlAgdSB2OiB1XHViYzg4IFx1YjE4ZFx1YzdhNVx1YWNmYyB2XHViYzg4IFx1YjE4ZFx1YzdhNSBcdWMwYWNcdWM3NzRcdWM3NTggXHVhY2JkXHViODVjXHVjNWQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViM2M0XHViODVjXHVjNWQwIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWQ1NThcdWIwOThcdWM1MjkgXHVjMmVjXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5RIHUgdjogdVx1YmM4OCBcdWIxOGRcdWM3YTVcdWFjZmMgdlx1YmM4OCBcdWIxOGRcdWM3YTUgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjZmZjXHViOWFjXHViOTdjIFx1YzIxOFx1ZDU4OVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMThkXHVjN2E1XHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWMyMTggTSgxICZsZTsgTiwgTSAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOLTFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViMThkXHVjN2E1XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNmZmNcdWI5YWNcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNmZmNcdWI5YWNcdWIyOTQgXHVkNTVjIFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTAgd1x1YzY0MCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCB1LCB2XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgXHVkNjE1XHVjMmRkXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2ZmY1x1YjlhYyBRXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgXHViOWM4XHViMmU0LCBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1OTE2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR3Jhc3MgUGxhbnRpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGhhcyBOIGJhcnJlbiBwYXN0dXJlcyAoMiAmbHQ7PSBOICZsdDs9IDEwMCwwMDApIGNvbm5lY3RlZCBieSBOLTEgYmlkaXJlY3Rpb25hbCByb2Fkcywgc3VjaCB0aGF0IHRoZXJlIGlzIGV4YWN0bHkgb25lIHBhdGggYmV0d2VlbiBhbnkgdHdvIHBhc3R1cmVzLiBCZXNzaWUsIGEgY293IHdobyBsb3ZlcyBoZXIgZ3JhemluZyB0aW1lLCBvZnRlbiBjb21wbGFpbnMgYWJvdXQgaG93IHRoZXJlIGlzIG5vIGdyYXNzIG9uIHRoZSByb2FkcyBiZXR3ZWVuIHBhc3R1cmVzLiBGYXJtZXIgSm9obiBsb3ZlcyBCZXNzaWUgdmVyeSBtdWNoLCBhbmQgdG9kYXkgaGUgaXMgZmluYWxseSBnb2luZyB0byBwbGFudCBncmFzcyBvbiB0aGUgcm9hZHMuIEhlIHdpbGwgZG8gc28gdXNpbmcgYSBwcm9jZWR1cmUgY29uc2lzdGluZyBvZiBNIHN0ZXBzICgxICZsdDs9IE0gJmx0Oz0gMTAwLDAwMCkuPFwvcD5cclxuXHJcbjxwPkF0IGVhY2ggc3RlcCBvbmUgb2YgdHdvIHRoaW5ncyB3aWxsIGhhcHBlbjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5GSiB3aWxsIGNob29zZSB0d28gcGFzdHVyZXMsIGFuZCBwbGFudCBhIHBhdGNoIG9mIGdyYXNzIGFsb25nIGVhY2ggcm9hZCBpbiBiZXR3ZWVuIHRoZSB0d28gcGFzdHVyZXMsIG9yLDxcL2xpPlxyXG5cdDxsaT5CZXNzaWUgd2lsbCBhc2sgYWJvdXQgaG93IG1hbnkgcGF0Y2hlcyBvZiBncmFzcyBvbiBhIHBhcnRpY3VsYXIgcm9hZCwgYW5kIEZhcm1lciBKb2huIG11c3QgYW5zd2VyIGhlciBxdWVzdGlvbi48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5GYXJtZXIgSm9obiBpcyBhIHZlcnkgcG9vciBjb3VudGVyIC0tIGhlbHAgaGltIGFuc3dlciBCZXNzaWUmIzM5O3MgcXVlc3Rpb25zITxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgTiBhbmQgTTxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGRlc2NyaWJpbmcgdGhlIGVuZHBvaW50cyBvZiBhIHJvYWQuPFwvbGk+XHJcblx0PGxpPkxpbmVzIE4rMS4uTitNOiBMaW5lIGkrMSBkZXNjcmliZXMgc3RlcCBpLiBUaGUgZmlyc3QgY2hhcmFjdGVyIG9mIHRoZSBsaW5lIGlzIGVpdGhlciBQIG9yIFEsIHdoaWNoIGRlc2NyaWJlcyB3aGV0aGVyIG9yIG5vdCBGSiBpcyBwbGFudGluZyBncmFzcyBvciBzaW1wbHkgcXVlcnlpbmcuIFRoaXMgaXMgZm9sbG93ZWQgYnkgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBBX2kgYW5kIEJfaSAoMSAmbHQ7PSBBX2ksIEJfaSAmbHQ7PSBOKSB3aGljaCBkZXNjcmliZSBGSiYjMzk7cyBhY3Rpb24gb3IgcXVlcnkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmVzIDEuLj8/PzogRWFjaCBsaW5lIGhhcyB0aGUgYW5zd2VyIHRvIGEgcXVlcnksIGFwcGVhcmluZyBpbiB0aGUgc2FtZSBvcmRlciBhcyB0aGUgcXVlcmllcyBhcHBlYXIgaW4gdGhlIGlucHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > USA Computing Olympiad > 2011-2012 Season > USACO December 2011 Contest > Gold 3번

  • 문제의 오타를 찾은 사람: hansc0320
  • 잘못된 데이터를 찾은 사람: hellogaon