Binary Tree: Subtree Sum, Maximum Path Sum, and Path Nodes

Given a valid binary tree rooted at node 0, compute the sum of all node values in the tree and the maximum non-empty simple path sum between any two nodes, and output one path of node values that achieves the maximum sum. A path follows parent-child edges, may start and end at any node, and cannot repeat nodes; single-node paths are allowed. Node values may be negative, zero, or repeated. This site keeps the three results of the original problem and adds a fourth line with the path of 0-based node IDs, to verify the path's validity when values repeat; this is an extension of this site's judging protocol, not a requirement of the original problem. When there are several optimal paths, any one may be output, in either the forward or the reverse direction.

输入格式

The first line contains n; the second line contains n integers values[i]; in each of the next n lines, line i contains two integers left right, the left and right children of node i, where -1 means none. Complete original constraints: 1≤n≤200000, -10^9≤values[i]≤10^9. Node 0 is the root, all nodes are reachable from the root, and they form a valid binary tree; the numbering is not guaranteed to follow topological order. This site limits a single test input to 32 MiB.

输出格式

Output exactly four lines: the first line is the sum of all node values in the tree; the second line is the maximum non-empty path sum; the third line lists the node values of that path, separated by spaces; the fourth line lists the 0-based node IDs corresponding one-to-one to the third line, separated by spaces. The path contains at least one node, no ID may repeat, and adjacent IDs must be joined by a parent-child edge. Any optimal path is accepted; it does not have to match the reference output. The fourth line is this site's extension.

样例 1

输入：

3
1 2 3
1 2
-1 -1
-1 -1

输出：

6
6
2 1 3
1 0 2

样例 2

输入：

3
-8 -2 -3
1 2
-1 -1
-1 -1

输出：

-13
-2
-2
1

样例 3

输入：

3
0 0 0
1 2
-1 -1
-1 -1

输出：

0
0
0
0

样例说明

In the original example, the tree sum is 6 and the maximum path 2→1→3 has sum 6; this site adds the ID path 1→0→2. In the all-negative example, the best is the single node -2 (ID1); you cannot choose an empty path to get 0. In the all-zero example, any single node or any valid path is optimal.