시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 36 8 5 19.231%

문제

Byteasar는 새로운 궁전을 지었다. 그 궁전은 N개의 방과 N-1개의 통로가 방을 잇고 있다. 각각의 통로는 정확히 두 개의 방을 연결한다. 방은 1부터 N까지 번호를 가지며, 궁전으로 가는 유일한 입구는 1번 방이다. 모든 방은 입구에서부터의 경로가 유일하다. 즉, 방들은 트리 구조를 이루고 있다.

이 궁전의 소방국장은 건물 내부에 소화기를 배치하려 한다. 그는 다음의 규칙대로 소화기를 배치할 것이다.

  • 소화기는 방 안에 배치되어야 하며, 하나의 방은 소화기를 몇 개라도 가질 수 있다.
  • 하나의 소화기는 그 소화기가 위치한 방에서 K개의 통로 이내에 떨어져 있는 방까지 지킬 수 있다. 이를 소화기의 '영역'이라 하자.
  • 각각의 방은 하나 이상의 소화기의 영역에 들어야 한다. 
  • 각 소화기는 최대 S개의 방을 구역으로 가질 수 있다.

Byteasar는 궁전을 짓느라 국고 대부분을 탕진한 상태다. 따라서 그는 궁전의 모든 방을 화재의 위험에서 벗어나도록 하는 소화기의 배치 중 최소 개수의 소화기가 배치되기를 원한다. Byteasar를 도와주자!

입력

표준 입력의 첫 줄은 N, S, K가 공백을 두고 입력된다. (1 ≤ N ≤ 100,000, 1 ≤ S ≤ N, 1 ≤ K ≤ 20) 다음으로 N-1줄 동안 두 개의 정수가 공백을 두고 입력된다. i+1번째 줄은 xi와 yi를 입력받는데, 이는 xi와 yi를 연결하는 간선이라는 뜻이다.

출력

필요한 최소 개수의 소화기를 출력하여라.

예제 입력 1

12 3 1
1 12
3 8
7 8
8 9
2 12
10 12
9 12
4 8
5 8
8 11
6 8

예제 출력 1

4

힌트

W3sicHJvYmxlbV9pZCI6IjgxNjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWQ2NTRcdWFlMzAgXHVjMTI0XHVjZTU4IiwiZGVzY3JpcHRpb24iOiI8cD5CeXRlYXNhclx1YjI5NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhZDgxXHVjODA0XHVjNzQ0IFx1YzljMFx1YzVjOFx1YjJlNC4gXHVhZGY4IFx1YWQ4MVx1YzgwNFx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YmMyOVx1YWNmYyBOLTFcdWFjMWNcdWM3NTggXHVkMWI1XHViODVjXHVhYzAwIFx1YmMyOVx1Yzc0NCBcdWM3ODdcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMWI1XHViODVjXHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmMyOVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIFx1YmMyOVx1Yzc0MCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljMFx1YmE3MCwgXHVhZDgxXHVjODA0XHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWM3MjBcdWM3N2NcdWQ1NWMgXHVjNzg1XHVhZDZjXHViMjk0IDFcdWJjODggXHViYzI5XHVjNzc0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHViYzI5XHVjNzQwIFx1Yzc4NVx1YWQ2Y1x1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzIwXHVjNzdjXHVkNTU4XHViMmU0LiBcdWM5ODksIFx1YmMyOVx1YjRlNFx1Yzc0MCBcdWQyYjhcdWI5YWMgXHVhZDZjXHVjODcwXHViOTdjIFx1Yzc3NFx1YjhlOFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFkODFcdWM4MDRcdWM3NTggXHVjMThjXHViYzI5XHVhZDZkXHVjN2E1XHVjNzQwIFx1YWM3NFx1YmIzYyBcdWIwYjRcdWJkODBcdWM1ZDAgXHVjMThjXHVkNjU0XHVhZTMwXHViOTdjIFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjI5NCBcdWIyZTRcdWM3NGNcdWM3NTggXHVhZGRjXHVjZTU5XHViMzAwXHViODVjIFx1YzE4Y1x1ZDY1NFx1YWUzMFx1Yjk3YyBcdWJjMzBcdWNlNThcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzE4Y1x1ZDY1NFx1YWUzMFx1YjI5NCBcdWJjMjkgXHVjNTQ4XHVjNWQwIFx1YmMzMFx1Y2U1OFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJjMjlcdWM3NDAgXHVjMThjXHVkNjU0XHVhZTMwXHViOTdjIFx1YmE4NyBcdWFjMWNcdWI3N2NcdWIzYzQgXHVhYzAwXHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMxOGNcdWQ2NTRcdWFlMzBcdWIyOTQgXHVhZGY4IFx1YzE4Y1x1ZDY1NFx1YWUzMFx1YWMwMCBcdWM3MDRcdWNlNThcdWQ1NWMgXHViYzI5XHVjNWQwXHVjMTFjIEtcdWFjMWNcdWM3NTggXHVkMWI1XHViODVjIFx1Yzc3NFx1YjBiNFx1YzVkMCBcdWI1YThcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YmMyOVx1YWU0Y1x1YzljMCBcdWM5YzBcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViOTdjIFx1YzE4Y1x1ZDY1NFx1YWUzMFx1Yzc1OCAmIzM5O1x1YzYwMVx1YzVlZCYjMzk7XHVjNzc0XHViNzdjIFx1ZDU1OFx1Yzc5MC48XC9saT5cclxuXHQ8bGk+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YmMyOVx1Yzc0MCBcdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzE4Y1x1ZDY1NFx1YWUzMFx1Yzc1OCBcdWM2MDFcdWM1ZWRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1YzE4Y1x1ZDY1NFx1YWUzMFx1YjI5NCBcdWNkNWNcdWIzMDAgU1x1YWMxY1x1Yzc1OCBcdWJjMjlcdWM3NDQgXHVhZDZjXHVjNWVkXHVjNzNjXHViODVjIFx1YWMwMFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkJ5dGVhc2FyXHViMjk0IFx1YWQ4MVx1YzgwNFx1Yzc0NCBcdWM5ZDNcdWIyOTBcdWI3N2MgXHVhZDZkXHVhY2UwIFx1YjMwMFx1YmQ4MFx1YmQ4NFx1Yzc0NCBcdWQwZDVcdWM5YzRcdWQ1NWMgXHVjMGMxXHVkMGRjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVhZGY4XHViMjk0IFx1YWQ4MVx1YzgwNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViYzI5XHVjNzQ0IFx1ZDY1NFx1YzdhY1x1Yzc1OCBcdWM3MDRcdWQ1ZDhcdWM1ZDBcdWMxMWMgXHViYzk3XHVjNWI0XHViMDk4XHViM2M0XHViODVkIFx1ZDU1OFx1YjI5NCBcdWMxOGNcdWQ2NTRcdWFlMzBcdWM3NTggXHViYzMwXHVjZTU4IFx1YzkxMSBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHVjNzU4IFx1YzE4Y1x1ZDY1NFx1YWUzMFx1YWMwMCBcdWJjMzBcdWNlNThcdWI0MThcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0LiBCeXRlYXNhclx1Yjk3YyBcdWIzYzRcdWM2NDBcdWM4ZmNcdWM3OTAhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWQ0NWNcdWM5MDAgXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM3NDAgTiwgUywgS1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gKDEgJmxlOyBOJm5ic3A7JmxlOyAxMDAsMDAwLCAxICZsZTsgUyZuYnNwOyZsZTsgTiwgMSAmbGU7IEsmbmJzcDsmbGU7IDIwKSBcdWIyZTRcdWM3NGNcdWM3M2NcdWI4NWMgTi0xXHVjOTA0IFx1YjNkOVx1YzU0OCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHViNDUwXHVhY2UwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gaSsxXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0MCB4PHN1Yj5pPFwvc3ViPlx1YzY0MCB5PHN1Yj5pPFwvc3ViPlx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWIyOTRcdWIzNzAsIFx1Yzc3NFx1YjI5NCB4PHN1Yj5pPFwvc3ViPlx1YzY0MCB5PHN1Yj5pPFwvc3ViPlx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzc0XHViNzdjXHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWMxOGNcdWQ2NTRcdWFlMzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC84MTY5XC8xLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjE2MnB4OyB3aWR0aDoyODhweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODE2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpcmUgRXh0aW5ndWlzaGVycyIsImRlc2NyaXB0aW9uIjoiPHA+Qnl0ZWFzYXIgaGFzIGhhZCBhIG5ldyBwYWxhY2UgYnVpbHQuIEl0IGNvbnNpc3RzIG9mIG4gY2hhbWJlcnMgYW5kIG4tMSBjb3JyaWRvcnMgY29ubmVjdGluZyB0aGVtLiBFYWNoIGNvcnJpZG9yIGNvbm5lY3RzIGV4YWN0bHkgdHdvIGNoYW1iZXJzLiBUaGUgcm9vbXMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBUaGVyZSBpcyBvbmx5IGEgc2luZ2xlIGVudHJhbmNlIHRvIHRoZSBwYWxhY2UsIHdoaWNoIGxlYWRzIHRvIGNoYW1iZXIgbm8uIDEuIEZvciBlYWNoIGNoYW1iZXIgdGhlcmUgaXMgZXhhY3RseSBvbmUgcm91dGUgbGVhZGluZyB0byBpdCBmcm9tIHRoZSBlbnRyYW5jZSwgd2l0aG91dCB0dXJuaW5nIGJhY2sgb24gdGhlIHdheS4gSW4gb3RoZXIgd29yZHMsIHRoZSBjaGFtYmVycyBhbmQgdGhlIGNvcnJpZG9ycyBmb3JtIGEgdHJlZSAtIGEgY29ubmVjdGVkIGFjeWNsaWMgZ3JhcGguPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJlIG1hcnNoYWwgd2hvIGlzIHRvIGFwcHJvdmUgdGhlIGJ1aWxkaW5nIGRlbWFuZHMgcGxhY2luZyBmaXJlIGV4dGluZ3Vpc2hlcnMgaW5zaWRlLiBUaGUgZm9sbG93aW5nIGFyZSBoaXMgZXhhY3QgcmVxdWlyZW1lbnRzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBmaXJlIGV4dGluZ3Vpc2hlcnMgc2hvdWxkIGJlIHBsYWNlZCBpbiAoc29tZSkgY2hhbWJlcnMsIGFuZCBvbmUgY2hhbWJlciBtYXkgc3RvcmUgYW55IG51bWJlciBvZiBleHRpbmd1aXNoZXJzLjxcL2xpPlxyXG5cdDxsaT5FYWNoIGNoYW1iZXIgaGFzIHRvIGJlIGFzc2lnbmVkIG9uZSBmaXJlIGV4dGluZ3Vpc2hlciwgdGhvdWdoIGl0IG1heSBiZSBzdG9yZWQgaW4gYW5vdGhlciBjaGFtYmVyLjxcL2xpPlxyXG5cdDxsaT5FYWNoIGZpcmUgZXh0aW5ndWlzaGVyIGNhbiBiZSBhc3NpZ25lZCB0byBhdCBtb3N0ICZuYnNwO2RpZmZlcmVudCBjaGFtYmVycy48XC9saT5cclxuXHQ8bGk+Rm9yIGVhY2ggcm9vbSBpdHMgYXNzaWduZWQgZXh0aW5ndWlzaGVyIGlzIHdpdGhpbiB0aGUgcmFuZ2Ugb2YgayBjb3JyaWRvcnMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Qnl0ZWFzYXIgaGFzIGEgd2VlayBzcG90IGZvciBsYXZpc2ggcGFsYWNlcywgc28gaXQgaXMgbm8gc3VycHJpc2UgaGUgaGFzIHZlcnkgbGl0dGxlIG1vbmV5IG5vdywgcmlnaHQgYWZ0ZXIgY29tcGxldGlvbiBvZiBhbm90aGVyIHNwbGVuZGlkIHBhbGFjZS4gVGhlcmVmb3JlIGhlIGlzIGludGVyZXN0ZWQgaW4gdGhlIG1pbmltdW0gbnVtYmVyIG9mIGZpcmUgZXh0aW5ndWlzaGVycyBzdWZmaWNpZW50IGZvciBzYXRpc2Z5aW5nIGZpcmUgbWFyc2hhbCYjMzk7cyBkZW1hbmRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIHRocmVlIGludGVnZXJzIG4sIHMgYW5kIGsgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMsIDEgJmxlOyBuICZsZTsgMTAwLDAwMCwgMSAmbGU7IHMgJmxlOyBuLCAxICZsZTsgayAmbGU7IDIwLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgbi0xIGxpbmVzIGhvbGRzIHR3byBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIExpbmUgbm8uIGkrMSBjb250YWlucyB0aGUgbnVtYmVycyAxICZsZTsgeDxzdWI+aTxcL3N1Yj4gJmx0OyB5PHN1Yj5pPFwvc3ViPiAmbGU7IG4gZGVub3RpbmcgdGhlIGNvcnJpZG9yIGNvbm5lY3RpbmcgY2hhbWJlcnMgbm8uIHg8c3ViPmk8XC9zdWI+IGFuZCB5PHN1Yj5pPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCBpcyB0byBob2xkIG9uZSBpbnRlZ2VyIC0gdGhlIG1pbmltdW0gbnVtYmVyIG9mIGZpcmUgZXh0aW5ndWlzaGVycyB0aGF0IGhhdmUgdG8gYmUgaW5zdGFsbGVkIGluIHBhbGFjZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzgxNjlcLzEuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTYycHg7IHdpZHRoOjI4OHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=