AlgoUniversity
  • Go Back
Discussion
Robber On Tree :

Author

Shikhar Mehrotra

Difficulty Level : Hard

Submissions : 748

Asked In : Intuit

Marks :20

: 10 | : 2

You are given a rooted tree of $$$N$$$ nodes, numbered $$$1$$$ to $$$N$$$, with root as $$$1$$$. Each node $$$i$$$ in the tree has some number of coins denoted by $$$C_{i}$$$, representing the number of coins the $$$i_{th}$$$ node has.

At time $$$t = 0$$$, you are at the root node and there's a robber at one of the leaf nodes $$$R$$$. At each step, both you and the robber take one step each and move to an adjacent node.

To prevent chaos, there are some restrictions on both your and robber's movements. You have to choose a leaf node and take the shortest path to that leaf node and stop once you reach that leaf node. The robber has to take the shortest path to the root node and stop once the robber reaches the root node.

A person reaching a node first gets to take all the coins in the node leaving it empty for anyone who visits it after that time. If 2 people reach the node at the same time, they each get half of the coins in that node.

What's the maximum number of coins that you can aim to get in this process?

Input

First line contains a single integer $$$2\le N \le 10^{5}$$$ denoting number of nodes

Second line contains $$$N$$$ space-separated integers , where $$$i_{th}$$$ integer denotes $$$-10000\le C_{i} \le 10000$$$

Third line contains a single integer $$$1\le R \le N$$$

Following $$$N-1$$$ line contains two space separated integers $$$u$$$ and $$$v$$$ ,denoting edge between $$$u$$$ and $$$v$$$.

It is guaranteed $$$R$$$ is a leaf node and $$$C_{i}$$$ is even for all $$$i$$$

Output

Output maximum number of coins that you can aim to get in this process.

Example

Input
7
2 4 6 2 2 6 8
7
1 2
1 3
2 4
2 5
3 6
3 7
Output
11

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.