MapleTree | Topcoder Archive

Problem Statement

Time limit is 3.5 seconds.

Kaede loves maple trees. One day, she found a big maple tree and she described it as an undirected connected graph with N nodes and N-1 edges.

You are given the description in the int[]s p and length. For each valid i, the i-th edge of the tree connects node p[i] and node i+1, and the length of this edge is length[i].

There are 2^N-1 ways to choose a non-empty subset of nodes. Once we choose a subset of nodes, there is always a unique minimal subtree which contains all nodes in the subset.

Kaede got interested in diameters of these subtrees.

Suppose we iterate over all 2^N-1 ways to choose a non-empty subset of nodes, for each of them we construct the unique minimal subtree and then we determine and write down its diameter. Let D be the sum of the 2^N-1 values we would write down.

Please help Kaede: calculate and return the value (D modulo 1,000,000,007) for the given tree.

Definition

Class:: MapleTree
Method:: sum
Parameters:: int[], int[]
Returns:: int
Method signature:: int sum(int[] p, int[] length)
(be sure your method is public)

Notes

Given two vertices u, v in a tree, let d(u, v) be the distance between u and v, i.e., the sum of lengths on the unique simple path that connects u and v. The diameter of a tree is the largest out of all values d(u, v).

Constraints

N will be between 2 and 2000, inclusive.
p and length will contain exactly N-1 elements each.
For valid i, p[i] will be between 0 and i, inclusive.
Each element of length will be between 1 and 10000, inclusive.

Examples

```
{0, 0, 1, 1, 2}
```
```
{1, 2, 1, 1, 2}
```
```
Returns: 249
```
The tree is shown below as ASCII art. Edge lengths are shown using the corresponding number of symbols. 0 / \ 1 \ / \ 2 3 4 \ \ 5 The diameter of this tree is 6. There are 63 different ways in which we can select a non-empty subset of nodes, so the answer is a sum of 63 subtree diameters.
```
{0, 1, 2, 3}
```
```
{10, 10, 10, 10}
```
```
Returns: 720
```
This tree is a line. We can compute the answer as follows: There are 5 non-empty subsets of nodes that produce a subtree of diameter 0. Example subset: {2}. There are 4 non-empty subsets of nodes that produce a subtree of diameter 10. Example subset: {2, 3}. There are 6 non-empty subsets of nodes that produce a subtree of diameter 20. Example subsets: {0, 2} and {1, 2, 3}. There are 8 non-empty subsets of nodes that produce a subtree of diameter 30. Example subset: {0, 1, 3}. There are 8 non-empty subsets of nodes that produce a subtree of diameter 40. Example subset: {0, 1, 2, 3, 4}. Thus, the sum of all 31 diameters is 4*10 + 6*20 + 8*30 + 8*40 = 720.
```
{0, 0, 0, 0}
```
```
{10, 10, 10, 10}
```
```
Returns: 480
```
This tree is a star. Among the 31 subtrees whose diameters we are interested in are five with diameter 0, four with diameter 10, and twenty-two with diameter 20. Thus, the sum of all diameters is 4*10 + 22*20 = 480.
```
{0}
```
```
{1}
```
```
Returns: 1
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.