시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 254 144 75 45.181%

문제

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+XHVjZDA4XHVhZTMwXHVjNWQwIFx1YjA5OFx1YmIzNFx1YjI5NCBcdWQ1NWMgXHVhZGY4XHViOGU4XHViM2M0IFx1YzJlY1x1YWNhOFx1YzgzOCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LiBcdWNmZmNcdWI5YWNcdWI5N2MgXHVjMjE4XHVkNTg5XHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIxOGRcdWM3YTVcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVjZmZjXHViOWFjXHVjNzU4IFx1YzIxOCBNKDEgJmxlOyBOLCBNICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE4tMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViM2M0XHViODVjXHVhYzAwIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWIxOGRcdWM3YTVcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Y2ZmY1x1YjlhY1x1YjI5NCBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MCB3XHVjNjQwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IHUsIHZcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWQ2MTVcdWMyZGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZmZjXHViOWFjIFFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWI5YzhcdWIyZTQsIFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU5MTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHcmFzcyBQbGFudGluZyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFzIE4gYmFycmVuIHBhc3R1cmVzICgyICZsdDs9IE4gJmx0Oz0gMTAwLDAwMCkgY29ubmVjdGVkIGJ5IE4tMSBiaWRpcmVjdGlvbmFsIHJvYWRzLCBzdWNoIHRoYXQgdGhlcmUgaXMgZXhhY3RseSBvbmUgcGF0aCBiZXR3ZWVuIGFueSB0d28gcGFzdHVyZXMuIEJlc3NpZSwgYSBjb3cgd2hvIGxvdmVzIGhlciBncmF6aW5nIHRpbWUsIG9mdGVuIGNvbXBsYWlucyBhYm91dCBob3cgdGhlcmUgaXMgbm8gZ3Jhc3Mgb24gdGhlIHJvYWRzIGJldHdlZW4gcGFzdHVyZXMuIEZhcm1lciBKb2huIGxvdmVzIEJlc3NpZSB2ZXJ5IG11Y2gsIGFuZCB0b2RheSBoZSBpcyBmaW5hbGx5IGdvaW5nIHRvIHBsYW50IGdyYXNzIG9uIHRoZSByb2Fkcy4gSGUgd2lsbCBkbyBzbyB1c2luZyBhIHByb2NlZHVyZSBjb25zaXN0aW5nIG9mIE0gc3RlcHMgKDEgJmx0Oz0gTSAmbHQ7PSAxMDAsMDAwKS48XC9wPlxyXG5cclxuPHA+QXQgZWFjaCBzdGVwIG9uZSBvZiB0d28gdGhpbmdzIHdpbGwgaGFwcGVuOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkZKIHdpbGwgY2hvb3NlIHR3byBwYXN0dXJlcywgYW5kIHBsYW50IGEgcGF0Y2ggb2YgZ3Jhc3MgYWxvbmcgZWFjaCByb2FkIGluIGJldHdlZW4gdGhlIHR3byBwYXN0dXJlcywgb3IsPFwvbGk+XHJcblx0PGxpPkJlc3NpZSB3aWxsIGFzayBhYm91dCBob3cgbWFueSBwYXRjaGVzIG9mIGdyYXNzIG9uIGEgcGFydGljdWxhciByb2FkLCBhbmQgRmFybWVyIEpvaG4gbXVzdCBhbnN3ZXIgaGVyIHF1ZXN0aW9uLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZhcm1lciBKb2huIGlzIGEgdmVyeSBwb29yIGNvdW50ZXIgLS0gaGVscCBoaW0gYW5zd2VyIEJlc3NpZSYjMzk7cyBxdWVzdGlvbnMhPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBOIGFuZCBNPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk46IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgZGVzY3JpYmluZyB0aGUgZW5kcG9pbnRzIG9mIGEgcm9hZC48XC9saT5cclxuXHQ8bGk+TGluZXMgTisxLi5OK006IExpbmUgaSsxIGRlc2NyaWJlcyBzdGVwIGkuIFRoZSBmaXJzdCBjaGFyYWN0ZXIgb2YgdGhlIGxpbmUgaXMgZWl0aGVyIFAgb3IgUSwgd2hpY2ggZGVzY3JpYmVzIHdoZXRoZXIgb3Igbm90IEZKIGlzIHBsYW50aW5nIGdyYXNzIG9yIHNpbXBseSBxdWVyeWluZy4gVGhpcyBpcyBmb2xsb3dlZCBieSB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIEFfaSBhbmQgQl9pICgxICZsdDs9IEFfaSwgQl9pICZsdDs9IE4pIHdoaWNoIGRlc2NyaWJlIEZKJiMzOTtzIGFjdGlvbiBvciBxdWVyeS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZXMgMS4uPz8/OiBFYWNoIGxpbmUgaGFzIHRoZSBhbnN3ZXIgdG8gYSBxdWVyeSwgYXBwZWFyaW5nIGluIHRoZSBzYW1lIG9yZGVyIGFzIHRoZSBxdWVyaWVzIGFwcGVhciBpbiB0aGUgaW5wdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

  • 빠진 조건을 찾은 사람: 79brue
  • 문제의 오타를 찾은 사람: hansc0320
  • 잘못된 데이터를 찾은 사람: hellogaon