Robber On Tree :
Difficulty Level : Hard
Submissions : 723
Asked In :
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?
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 maximum number of coins that you can aim to get in this process.
7 2 4 6 2 2 6 8 7 1 2 1 3 2 4 2 5 3 6 3 7
11
