Festival Plan¶
- Indicative time limit: 3.5 s (environment and measurements).
- Deployment time limit: measure the reference program in the target environment, multiply the slowest case's median time by 2, and round up to the next 0.5 seconds.
- Memory limit: 512 MB.
Story¶
The festival team has arranged its events in a rooted tree. Following the tree downward gives a continuous program of events. Each event has a value; expensive events may have negative values.
A program must contain a permitted number of events. Any event might become the festival's highlight, so the team wants the best total value of a program containing each event.
(This story was rewritten by GPT-6.)
Formal Problem Statement¶
You are given an undirected tree with \(n\) vertices numbered \(1,\ldots,n\) , rooted at vertex \(1\) . Vertex \(i\) has weight \(v_i\) .
A valid path starts at any vertex and moves to a child at every step. Its number of vertices, including both endpoints, is between \(L\) and \(R\) , inclusive. Its value is the sum of the weights of its vertices.
For each vertex \(i\) , independently find the maximum value of a valid path containing \(i\) . Paths chosen for different answers may overlap.
Input Format¶
The first line contains \(n,L,R\) .
The second line contains \(n\) integers \(v_1,\ldots,v_n\) .
Each of the next \(n-1\) lines contains two integers \(u,v\) , describing an undirected edge.
Output Format¶
Print \(n\) lines. Line \(i\) contains the answer for vertex \(i\) , or -1061109568 if no valid path contains it. A valid path may have a negative value.
Sample 1¶
Input¶
5 2 5
-338 971 -35 -221 458
1 2
3 1
3 4
2 5
Output¶
1091
1429
-256
-256
1429
Sample 2¶
Input¶
1 1 1
-7
Output¶
-7
Sample 3¶
Input¶
4 3 4
2 -1 4 3
1 2
1 3
1 4
Output¶
-1061109568
-1061109568
-1061109568
-1061109568
Sample Explanation¶
In sample 1, path \(1\to2\to5\) has value \(1091\) , path \(2\to5\) has value \(1429\) , and path \(3\to4\) has value \(-256\) . Path \(5\to2\to1\to3\) is invalid because it does not always move to a child.
Vertex IDs appear inside the circles, with weights beside them. Arrows point from parents to children.
Sample 2 permits a single-vertex path. In sample 3, the longest downward path has only two vertices, so every answer is the no-path marker.
Constraints and Guarantees¶
For all test cases: \(1\le L\le R\le n\le500000\) , \(-1000\le v_i\le1000\) , and \(1\le u,v\le n\) . The input edges form a tree.
| Score | Additional restrictions |
|---|---|
| 100% | None |