Logo
(追記) (追記ここまで)

18372번 - 트리와 쿼리 14 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB209704729.012%

문제

N개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있다. 간선의 가중치는 모두 1이다.

아래의 쿼리를 수행하는 프로그램을 작성하시오.

  • k v1 r1 v2 r2 ... vk rk: 어떠한 정점 x가 vi와 거리 ri 이내에 있다면 (거리가 ri보다 작거나 같다면), x가 i번 조건을 만족한다고 하자. 트리에 있는 모든 정점들 중, 쿼리로 주어진 k개 조건 중 k-1개 이상의 조건을 만족하는 정점의 개수를 출력하라.

입력

첫 번째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 100,000)

이후 N-1개의 줄에는 각 간선이 연결하는 두 정점 번호 u, v가 주어진다. (1 ≤ u, v ≤ N)

다음 줄에 정수 M이 주어진다. (1 ≤ M ≤ 300,000)

이후 M개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다. 각 쿼리는 지문과 다르게 한 줄에 들어오지 않으며, k + 1개의 줄로 분리되어 주어진다. 예제 입력을 참고하라. (1 ≤ vi ≤ N, 0 ≤ ri < N, 1 ≤ k)

쿼리로 주어지는 k의 합은 300000을 넘지 않는다.

출력

쿼리의 결과를 한 줄에 하나씩 출력한다.

제한

예제 입력 1 

10
1 3
6 4
9 8
1 8
3 4
2 8
10 3
4 5
8 7
2
3
8 1
3 1
3 2
2
7 3
6 0

예제 출력 1 

5
7

힌트

W3sicHJvYmxlbV9pZCI6IjE4MzcyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI4XHViOWFjXHVjNjQwIFx1Y2ZmY1x1YjlhYyAxNCIsImRlc2NyaXB0aW9uIjoiPHA+Tlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1YzgxMFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMDBcdWM5MTFcdWNlNThcdWIyOTQgXHViYWE4XHViNDUwIDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OFx1Yzc1OCZuYnNwO1x1Y2ZmY1x1YjlhY1x1Yjk3YyBcdWMyMThcdWQ1ODlcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48Zm9udCBmYWNlPVwibW9ub3NwYWNlXCI+ayB2PHN1Yj4xPFwvc3ViPiByPHN1Yj4xPFwvc3ViPiB2PHN1Yj4yPFwvc3ViPiByPHN1Yj4yPFwvc3ViPiAuLi4gdjxzdWI+azxcL3N1Yj4gcjxzdWI+azxcL3N1Yj48XC9mb250PjogXHVjNWI0XHViNWEwXHVkNTVjIFx1YzgxNVx1YzgxMCB4XHVhYzAwIHY8c3ViPmk8XC9zdWI+XHVjNjQwIFx1YWM3MFx1YjlhYyByPHN1Yj5pPFwvc3ViPiBcdWM3NzRcdWIwYjRcdWM1ZDAgXHVjNzg4XHViMmU0XHViYTc0IChcdWFjNzBcdWI5YWNcdWFjMDAgcjxzdWI+aTxcL3N1Yj5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNFx1YmE3NCksIHhcdWFjMDAgaVx1YmM4OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVkMmI4XHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHViNGU0IFx1YzkxMSwgXHVjZmZjXHViOWFjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBrXHVhYzFjIFx1Yzg3MFx1YWM3NCBcdWM5MTEgay0xXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiZuYnNwOyZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE4tMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzgxMCBcdWJjODhcdWQ2MzggdSwmbmJzcDt2XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB1LCB2ICZsZTsgTik8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBNJm5ic3A7JmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWFjODNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWNmZmNcdWI5YWNcdWIyOTQgXHVjOWMwXHViYjM4XHVhY2ZjJm5ic3A7XHViMmU0XHViOTc0XHVhYzhjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNjI0XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgayArIDFcdWFjMWNcdWM3NTggXHVjOTA0XHViODVjIFx1YmQ4NFx1YjlhY1x1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjYzM4XHVhY2UwXHVkNTU4XHViNzdjLiAoMSAmbGU7IHY8c3ViPmk8XC9zdWI+ICZsZTsgTiwgMCAmbGU7IHI8c3ViPmkgPFwvc3ViPiZsdDsgTiwgMSAmbGU7IGspPFwvcD5cclxuXHJcbjxwPlx1Y2ZmY1x1YjlhY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQga1x1Yzc1OCBcdWQ1NjlcdWM3NDAgMzAwMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZmZjXHViOWFjXHVjNzU4IFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTgzNzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJbmZlcm5hcGUiLCJkZXNjcmlwdGlvbiI6IjxwPk1vbmtleXMgbGl2ZSBvbiB0aGUgdHJlZXMsIHJpZ2h0PyBJbmZlcm5hcGUgcHJvYmFibHkgdG9vLiBUaGVyZSBpcyBhIHRyZWUgd2l0aCBuIHZlcnRpY2VzIChhIHRyZWUgaXMgYSBjb25uZWN0ZWQgdW5kaXJlY3RlZCBncmFwaCB3aXRob3V0IGN5Y2xlcykgYW5kIHEgaW5kZXBlbmRlbnQgcXVlcmllcy4gVmVydGljZXMgYXJlIG51bWJlcmVkIHdpdGggaW50ZWdlcnMgZnJvbSAxIHRvIG4uPFwvcD5cclxuXHJcbjxwPkluIGVhY2ggcXVlcnksIHRoZXJlIGFyZSBrIEluZmVybmFwZSBpbiB0aGUgdmVydGljZXMgb2YgdGhlIHRyZWUgKGsgbWF5IGJlIGRpZmZlcmVudCBmb3IgZGlmZmVyZW50IHF1ZXJpZXMpLiBUaGUgaS10aCBvZiB0aGVtIHNpdHMgaW4gdGhlIHZlcnRleCB2PHN1Yj5pPFwvc3ViPiBhbmQgaGFzIHBvd2VyIHI8c3ViPmk8XC9zdWI+LiBJbmZlcm5hcGUgaGVhdHMgYWxsIHZlcnRpY2VzIHdoaWNoIGFyZSBpbiB0aGUgZGlzdGFuY2UgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIGl0cyBwb3dlciBmcm9tIHY8c3ViPmk8XC9zdWI+LiBUaGUgZGlzdGFuY2UgYmV0d2VlbiB0d28gdmVydGljZXMgaXMgdGhlIG51bWJlciBvZiBlZGdlcyBvbiB0aGUgc2hvcnRlc3QgcGF0aCBiZXR3ZWVuIHRoZW0uIFRoZSBwb3dlcnMgYXJlIG5vbi1uZWdhdGl2ZSwgc28gZWFjaCBJbmZlcm5hcGUgYWx3YXlzIGhlYXRzIGl0cyBvd24gdmVydGV4LiBZb3VyIHRhc2sgaXMgdG8gYW5zd2VyIGhvdyBtYW55IHZlcnRpY2VzIGFyZSBoZWF0ZWQgYnkgYXQgbGVhc3QgayAmbWludXM7IDEgSW5mZXJuYXBlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgb25lIGludGVnZXIgbiAoMiAmbGU7IG4gJmxlOyAxMDAgMDAwKSAmbWRhc2g7IHRoZSBudW1iZXIgb2YgdmVydGljZXMgaW4gdGhlIHRyZWUuPFwvcD5cclxuXHJcbjxwPlRoZSBpLXRoIG9mIHRoZSBuZXh0IG4gJm1pbnVzOyAxIGxpbmVzIGRlc2NyaWJlcyB0aGUgaS10aCBlZGdlIG9mIHRoZSB0cmVlIGFuZCBjb250YWlucyB0d28gaW50ZWdlcnMgYTxzdWI+aTxcL3N1Yj4gYW5kIGI8c3ViPmk8XC9zdWI+ICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmk8XC9zdWI+ICZsZTsgbikgJm1kYXNoOyB0aGUgZW5kcG9pbnRzIG9mIHRoaXMgZWRnZS48XC9wPlxyXG5cclxuPHA+SXQmcnNxdW87cyBndWFyYW50ZWVkIHRoYXQgdGhlIGVkZ2VzIGRlc2NyaWJlIGEgY29ycmVjdCB0cmVlLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIHEgKDEgJmxlOyBxKSAmbWRhc2g7IHRoZSBudW1iZXIgb2YgcXVlcmllcy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIHEgYmxvY2tzIGRlc2NyaWJlcyBvbmUgcXVlcnkuPFwvcD5cclxuXHJcbjxwPkVhY2ggYmxvY2sgc3RhcnRzIHdpdGggYSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciBrICgyICZsZTsgayAmbGU7IDMwMCAwMDApICZtZGFzaDsgdGhlIG51bWJlciBvZiBJbmZlcm5hcGUgaW4gdGhlIGN1cnJlbnQgcXVlcnkuPFwvcD5cclxuXHJcbjxwPk5leHRseSwgZWFjaCBibG9jayBjb250YWlucyBrIGxpbmVzLiBUaGUgaS10aCBvZiB0aGVtIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB2PHN1Yj5pPFwvc3ViPiBhbmQgcjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyB2PHN1Yj5pPFwvc3ViPiAmbGU7IG4sIDAgJmxlOyByPHN1Yj5pPFwvc3ViPiAmbGU7IG4mbWludXM7MSkgJm1kYXNoOyB0aGUgaW5kZXggb2YgdGhlIHZlcnRleCBhdCB3aGljaCB0aGUgaS10aCBJbmZlcm5hcGUgc2l0cyBhbmQgdGhlIHBvd2VyIG9mIHRoaXMgSW5mZXJuYXBlLjxcL3A+XHJcblxyXG48cD5UaGUgc3VtIG9mIGsgb3ZlciBhbGwgcXVlcmllcyBpbiBvbmUgdGVzdCBkb2VzbiZyc3F1bzt0IGV4Y2VlZCAzMDAgMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBxIGxpbmVzLiBUaGUgaS10aCBvZiB0aGVtIHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgdmVydGljZXMgaGVhdGVkIGJ5IGF0IGxlYXN0IGFsbCBidXQgb25lIEluZmVybmFwZSBpbiB0aGUgaS10aCBxdWVyeS48XC9wPlxyXG4iLCJoaW50IjoiPHA+SGVyZSZyc3F1bztzIGhvdyB0aGUgdHJlZSBpbiB0aGUgc2FtcGxlIHRlc3QgbG9va3MgbGlrZTo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9kNGE5MDQ3Ny01NjRlLTQwNjgtYjhkOS0yNjI2YTRlZjQ5MjhcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDI2MHB4OyBoZWlnaHQ6IDE1NHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5BbmQgaGVyZSBpcyBob3cgdGhlIHF1ZXJpZXMgbG9vayBsaWtlOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzBmYWZmMjBlLTIwNTQtNDU3MS1hNDI0LWQwM2M5NDNiOWQyMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTAwcHg7IGhlaWdodDogMTcxcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSByZWQgYXJlYSBpcyBoZWF0ZWQgYnkgYWxsIEluZmVybmFwZSB3aGlsZSB0aGUgb3JhbmdlIG9uZSBpcyBoZWF0ZWQgYnkgYWxsIGJ1dCBvbmUuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Camp > Petrozavodsk Programming Camp > Summer 2019 > Day 5: Radewoosh + mnbvmar Contest I번

Contest > Open Cup > 2019/2020 Season > Stage 2: Grand Prix of Warsaw I번

  • 문제를 번역한 사람: koosaga
(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /