What is the maximal difference in the number of pigeons we can make by dropping some breadcrumbs while running through the park? It is obvious from the description that the park represents a tree where each statue is a node and each path is an edge.

Exhaustive search. The tree has ~\mathcal O(n^2)~ possible paths in it, each determined by its beginning and end. On a path, we have ~\mathcal O(2^n)~ possible ways to drop the crumbs. The exhaustive search can simulate all the possible strategies in ~\mathcal O(n^2 2^n)~ time complexity.

Greedy approach. To approach the problem better, we must first make some observations. Let us say Jerry is currently stationed in node ~v~ and arrived here from node ~t~. Jerry will visit node ~w~ in the next step. Let us denote ~N(v) = \sum_{(v,x) \in E} p_x~ number of pigeons in all the neighbours of the node ~v~. The gain ~g(v)~ from dropping a breadcrumb is ~g(v) = N(v)-p_t~ regardless of where the other breadcrumbs were dropped.

If a node ~x~ is neighbour to the ~v~ and ~w \ne x \ne t~, the observation is quite straightforward. If we drop the breadcrumb at node ~v~, ~p_x~ pigeons will be added to the path Tom traverses, otherwise not. Pigeons from node ~t~ do not affect Jerry's path, nor do they affect Tom's path. Jerry already met them once (and won't meet them again, even if they moved to node ~v~) and Tom will only meet them once regardless of their position. Pigeons from node ~w~ move to node ~v~, which means they won't count toward a total number of pigeons Jerry met. They will count towards the total number of pigeons Tom met. The values ~p_x~ that counted toward gain ~g(v)~ have not been changed from the start. Jerry has not yet reached these nodes or any of their neighbours. Hence the gain of dropping a breadcrumb at a node ~v~ only depends on the last visited node.

If the starting node of a walk is known in advance, all the gains ~g(v)~ can be calculated in advance. Now all we have to do is determine an ending point in such a way that the sum of the top ~v~ gains will be maximal. This can be done with a depth first search by storing all the gains on the current path in a priority queue and selecting the top ~v~. This approach takes ~\mathcal O(nv \log v)~ time if we know the starting node or ~\mathcal O(n^2 v \log v)~ if we have to try every possible initial node.

Dynamic programming. Let us root the tree in node ~i~. Let us denote ~c[i][j]~ maximal difference we can make by starting a path in node ~i~ and continuing in one of its subtrees, dropping at most ~j~ breadcrumbs in the subtree. Let us denote ~b[i][j]~ maximal difference we can make by starting a path in a subtree of a node ~i~ and ending it in ~i~, dropping at most ~j~ breadcrumbs in subtree or at node ~i~. Values of these two can easily be computed from values of ~b~ and ~c~ of ~i^\text{th}~ children. ~k~ denotes the children of node ~i~.

$$\displaystyle \begin{align*} c[i][0] &= 0 \\ c[i][j] &= \max_k (c[k][j], c[k][j-1]+g(k)-p_i) \\ b[i][0] &= 0 \\ b[i][j] &= \max_k (b[k][j], b[k][j-1]+g(i)-p_k) \end{align*}$$

The best path running through node ~i~ and its subtrees makes the difference ~\max_{j=1}^v b[i][j]+c[k][v-j]~. Note that the path must not begin and end in the same subtree. A way to achieve this is to temporarily store the best two values for each possible ~b[i][j], c[i][j]~ and in which subtree that path started/ended. The best solution which does not use the same subtree twice can be easily calculated from these. This approach takes ~\mathcal O(nv)~ time.