All Tracks Algorithms Graphs Depth First Search Problem

It's Christmas.
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

Problem Statement:

It is Christmas in New York. This time Monica decided to decorate the Christmas tree using the colors Red and Black. Now Phoebe and Rachel also want to decorate the tree but Monica want to do all the work by herself so she gave them a problem to keep them busy. Since Phoebe and Rachel want to solve this problem as fast as possible so they need your help.

You are given a tree comprising of N nodes numbered 1-N. Each node can either be Red or Black (0 denotes Red and 1 denotes Black).The tree is rooted at node number 1. Root of the tree is at level number 1. You need to answer Q queries. In each query you will be given a level (X) and among all nodes in that level you need to find out the node which have maximum number of black nodes in its subtree an also the maximum number of black nodes. If there are multiple answers , print the minimum numbered node along with maximum black nodes in its subtree. The level of a node is defined by 1 + (the number of connections between the node and the root).

INPUT

Initial input is T (test-cases) and for each test case-

First line contains an integer representing N the number of nodes. Next line contain n integers ,each representing the value(Ai) associated with each node from 1 to N (0 denotes Red and 1 denotes Black).

Next N - 1 lines contain two integers U and V each, which means that vertex U and V are connected to each other.

Next line contains an integer Q, the number of Queries. Next Q lines contain an integer X as described in the problem statement.

OUTPUT

For each query print 2 integers(node number and the number of black nodes in its subtree) separated by space in a new line. If the level(X) does not exist ,then print -1 in a new line.

CONSTRAINTS

1<=T<=100

1<=N<=40000

1<=Q<=10000

0<=Ai<=1

Author-Akshay Vasandani

SAMPLE INPUT
1
5
1 0 1 0 1
1 2
1 3
3 4
3 5
1
2
SAMPLE OUTPUT
3 2
Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications