{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/OCT14/mandarin/BTREE.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/OCT14/russian/BTREE.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003eThere is a country whose road system is a tree, the nodes in the tree represent cities and the edge is the road between them, and each edge is of unit length. For safety, the government should put guards to protect all cities. But the government is in shortage of money. So they might not be able to protect all cites.\u003c/p\u003e\r\n\r\n\u003cp\u003eYou\u0027re concerned about the country\u0027s safety, so you get the information of the guards. And you know that on the i-th day, there are k[i] guards on the road system, and j-th guard is on node a[j] and can protect every node whose distance to a[j] is not larger than r[j]. And you want to know how many nodes in the road system is protected by at least one guard.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line contains an integer n, denoting the number of the cities.\u003c/p\u003e\r\n\u003cp\u003eThen n-1 lines follows, each line contains 2 integers a and b, denoting there is an edge between city a and b (1-based index).\u003c/p\u003e\r\n\u003cp\u003eThe next line contains an integer Q, denoting the number of the days.\u003c/p\u003e\r\n\u003cp\u003eThen Q lines\u0027s description follows, each contains an integer k, denoting the number of guards in that day, and k integer pairs a[i],r[i] denoting the guards\u0027s information, for simplicity, no node will have more than 1 guard.\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e 1 ≤ n, Q ≤ 50000. \u003c/li\u003e\r\n\u003cli\u003e The total number of guards in the queries ≤ 500000. \u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each day, output the answer in one line.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cstrong\u003eInput:\u003c/strong\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n20\r\n1 2\r\n1 3\r\n1 4\r\n4 5\r\n4 6\r\n2 7\r\n4 8\r\n5 9\r\n7 10\r\n2 11\r\n9 12\r\n8 13\r\n1 14\r\n12 15\r\n9 16\r\n7 17\r\n12 18\r\n1 19\r\n6 20\r\n5\r\n2 9 3 12 5 \r\n3 3 3 4 1 11 5 \r\n3 3 3 10 4 19 2 \r\n2 3 4 10 2 \r\n5 5 4 11 2 16 2 18 1 19 2\r\n\u003c/pre\u003e\r\n\r\n\u003cpre\u003e\u003cstrong\u003eOutput:\u003c/strong\u003e\u003c/pre\u003e\r\n\u003cpre\u003e\r\n16\r\n16\r\n13\r\n16\r\n18\r\n\u003c/pre\u003e"}}]}