We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. HourRank 20
  3. Birjik and Nicole's Tree Game

Birjik and Nicole's Tree Game

Problem
Submissions
Leaderboard
Discussions
Editorial

Nicole and Birjik are seniors taking a break from job applications by creating the following game:

  • Birjik draws a rooted tree with vertices numbered from to , rooted at vertex .
  • Nicole creates queries. For each query, she takes a copy of the tree and colors of its vertices black, leaving the remaining vertices white.
  • The goal of the game is to answer each query by finding the respective values of , where each is the number of subtrees containing exactly black vertices (including the subtree's root vertex).

For example, the diagram below depicts a query on a tree where and the black vertices are , , and :

image

Given the tree and queries, solve each query by printing the values of on a new line.

Input Format

The first line contains an integer, , denoting the number of vertices of the tree.
Each of the subsequent lines contains two space-separated integers, and , describing an edge connecting vertices and .
The next line contains an integer, , denoting the number of queries. The subsequent lines describe each query over two lines:

  1. The first line contains an integer denoting .
  2. The second line contains space-separated integers describing the respective IDs of the vertices to color black.

Constraints

  • It is guaranteed that the given graph is a tree.
  • It is guaranteed that the vertex IDs given in each query are distinct IDs that exist in the tree.
  • The sum of over all queries in a test case is

Output Format

For each query, print a single line containing integers describing the respective values of . Recall that each is the total number of subtrees containing exactly black vertices.

Sample Input 0

7
1 2
1 3
1 4
2 5
3 7
3 6
2
3
5 7 2
3
7 6 5

Sample Output 0

2 3 1 1
1 4 1 1

Explanation 0

In this example, the graph and queries look like this:

image

We perform the following queries:

  1. Color vertices , , and black:

    image

    We then print the respective values of as 2 3 1 1 on a new line.

  2. Color vertices , , and black:

    image

    We then print the respective values of as 1 4 1 1 on a new line.

Sample Input 1

7
2 1
1 3
4 1
7 4
3 5
3 6
3
3
5 2 1
4
7 6 2 4
2
3 1

Sample Output 1

3 3 0 1
1 4 1 0 1
5 1 1

Explanation 1

In this example, the graph and queries look like this:

image

Follow the same process as Sample Case 0 to verify the Expected Output values.

Author

Birjik

Difficulty

Expert

Max Score

80

Submitted By

143

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download all test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature