Breaking the Tree
All submissions for this problem are available.
You are given a tree with N vertices where each vertex has an associated weight A[i]. Let’s call the sum of all weights in a tree W. Removing any edge from the tree will result in two trees, with the sums of each tree being, W1 and W2. You will be given Q queries. Each query will have an integer D-short for difference. You should output whether it is possible to remove an edge from the tree, breaking it into two different trees so that|W1 - W2| = D where |x| is the absolute value of x. If this is possible then output “Yes”, otherwise “No”. All queries are independent of each other. .
InputThe first line of each test case contains two integer N, Q denoting the number of vertices in the trees and number of queries respectively. The next line has N integers, A, the values associated to the node.The next N-1 lines each contain 2 integers u and v denoting an edge between vertex u and v. The next Q lines have 1 integer D.
OutputFor each query output "Yes" or "No" in a new line(without quotes).
Input: 6 4 1 5 7 3 9 2 1 2 1 3 3 4 3 5 5 6 5 27 40 21 Output: Yes No No Yes
Example case 1. For the first query the answer is "Yes" because the edge between 5 and 6 can be removed. For the second query, it is not possible to remove an edge and get a difference of 27.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions
If you are still having problems, see a sample solution here.