MapleTree

SRM 799 · 2021-02-04 · by IH19980412

SRM 799 · 2021-02-04 · by IH19980412 · Graph Theory, Simple Math

Show categories

Class Name: MapleTree

Return Type: int

Method Name: sum

Arg Types: (vector<int>, vector<int>)

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.

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

{0,0,0,0,3,4,6,7,4,5,2,8,5,9,14,14,13,0,16,8,5,2,19,6,6,17,18,16,9,16,6,25,11,12,0,21,0,13,15,24,28,7,19,38,31,16,29,39,16,37,31,17,42,16,39,48,7,27,23,2,6,55,34,35,51,52,32,28,11,63,61,58,19,16,48,15,0,36,47,1,21,45,75,81,28,15,23,53,58,67,87,69,83,12,45,87,92,58,2,85,43,93,57,103,1,14,43,81,46,58,6,5,90,1,80,8,63,96,107,93,76,32,0,91,94,80,119,34,74,9,57,10,95,102,75,11,129,91,16,87,55,37,113,17,69,76,132,106,66,91,127,112,145,107,102,15,60,125,67,129,127,78,162,47,66,43,97,96,117,53,72,89,26,75,87,55,122,86,48,1,99,93,71,8,130,90,3,5,11,56,150,180,65,171,57,158,114,114,36,5,80,104,13,90,152,28,192,65,26,30,86,122,13,106,176,106,177,110,23,206,194,157,82,158,49,215,163,223,43,40,47,78,230,18,43,182,193,59,97,188,210,7,71,130,144,98,14,184,183,51,8,144,13,108,119,81,205,190,185,102,203,131,178,128,51,178,178,205,179,74,33,66,66,121,8,53,45,47,17,13,187,162,81,82,233,261,190,257,110,38,137,82,231,41,263,99,117,260,187,214,129,158,240,96,275,223,238,13,11,15,13,161,246,290,273,240,70,285,250,222,267,305,273,229,178,11,270,276,319,175,98,154,67,108,18,49,285,291,196,285,158,169,127,343,187,253,303,176,3,158,294,126,85,325,32,211,122,65,330,23,241,255,259,114,95,122,190,239,262,104,239,287,185,369,35,261,329,321,81,285,292,21,363,150,367,264,272,172,174,279,160,228,88,114,288,365,193,319,120,231,234,358,253,243,326,300,123,345,311,77,31,186,147,124,126,254,243,79,375,265,17,247,364,99,79,171,189,395,400,266,270,184,224,159,210,390,11,420,195,431,207,151,380,115,87,226,289,79,360,36,119,361,282,344,177,97,249,346,22,360,189,316,152,292,401,447,434,80,231,183,191,287,77,89,67,236,388,5,1,60,334,22,432,86,6,445,68,382,274,167,480,423,90,234,324,456,71,442,44,452,14,435,301,193,321,116,79,434,416,365,377,469,374,22,470,367,503,205,90,225,415,285,220,284,160,436,152,163,313,297,18,47,502,75,489,468,412,485,182,459,180,179,211,121,186,92,423,1,461,509,470,457,185,518,330,545,516,482,420,527,352,371,48,112,456,174,389,505,485,198,209,422,446,341,75,527,390,85,404,399,548,102,69,4,243,16,157,123,139,23,8,508,211,566,106,204,408,325,457,539,332,56,259,155,72,429,451,325,28,233,433,438,436,315,508,501,67,111,587,292,447,250,501,611,198,124,101,495,410,365,464,365,186,109,161,84,152,254,637,305,303,435,123,402,478,605,62,563,438,170,284,205,517,101,376,240,563,62,202,299,479,540,396,75,573,346,19,139,432,637,129,134,253,321,666,316,383,499,118,394,572,30,259,371,48,391,150,225,630,532,466,336,313,453,233,378,178,608,482,294,656,139,263,124,367,617,489,394,627,435,125,55,388,167,460,596,249,474,514,501,537,497,132,420,22,525,18,481,169,561,435,131,299,434,220,426,400,208,498,405,165,493,385,507,68,702,253,620,311,487,67,204,709,349,23,337,736,237,106,302,537,41,269,502,684,760,681,356,17,367,359,587,451,156,357,766,573,767,458,541,28,212,534,273,405,379,133,472,288,418,388,625,786,22,359,393,665,393,242,189,141,301,489,6,645,204,321,444,805,124,258,422,654,396,511,780,534,493,376,577,256,172,438,587,324,681,542,712,296,230,749,711,409,618,306,255,656,326,749,581,446,431,498,294,600,118,298,616,95,306,658,805,522,71,645,17,374,490,355,466,378,436,142,338,507,98,567,715,786,708,693,446,297,455,859,423,559,223,465,819,816,641,391,194,204,310,407,723,709,255,8,491,425,422,562,231,332,701,831,747,119,170,200,48,743,659,99,495,328,301,185,740,468,869,566,877,19,212,558,682,885,542,198,427,566,104,640,545,136,465,4,827,279,264,459,514,870,324,613,735,933,594,87,401,194,6,54,43,222,623,366,931,185,752,1,168,654,603,707,862,290,445,549,517,705,415,225,366,172,791,258,439,434,207,218,436,264,959,835,325,951,7,416,953,245,724,446,781,413,160,445,475,171,709,159,509,771,640,343,407,830,940,155,808,389,696,864,924,76,997,583,758,186,229,672,686,390,482,693,583,768,694,281,657,188,756,245,278,883,813,889,322,625,983,38,809,935,557,854,569,435,257,877,641,477,485,723,759,869,230,916,774,991,327,1041,343,953,931,711,550,336,212,969,122,147,267,709,64,646,642,401,717,598,951,886,354,91,777,192,723,798,472,95,1049,179,414,243,1042,188,567,1078,331,472,476,448,95,651,1063,298,503,131,530,888,262,1079,364,287,411,635,473,1011,1089,477,472,383,78,721,959,769,262,331,760,278,88,1016,702,1034,144,727,1097,235,158,492,290,315,106,203,955,540,444,29,367,493,966,52,509,1017,980,609,877,914,548,1125,906,272,136,625,607,450,300,828,322,1137,1135,29,118,151,355,791,340,726,328,20,727,900,201,573,894,746,875,897,158,959,38,19,57,794,1099,548,297,245,644,1008,822,246,254,95,661,1100,790,453,1157,465,839,1000,798,76,289,947,113,895,976,176,952,292,155,71,497,1,855,155,52,780,927,1110,1214,757,233,983,1210,267,543,77,958,585,1223,21,1160,849,472,988,1120,32,73,1222,486,620,1070,60,22,203,743,1228,94,351,1124,1163,1240,11,1008,274,1038,140,1074,1258,1056,1264,711,1057,115,253,936,502,1156,471,1095,703,971,140,806,846,1164,415,548,1282,242,257,682,804,982,502,926,531,209,690,1166,721,285,1091,346,1010,22,632,433,724,144,316,698,651,1,31,301,674,767,333,1241,595,1276,635,27,410,48,1244,1074,982,1180,305,1242,963,374,101,1059,828,852,1264,1327,1246,1131,1196,440,127,948,124,653,859,568,780,1317,369,614,919,469,23,1063,542,586,112,684,957,721,615,465,1172,860,333,1338,1172,656,314,1362,140,1129,1118,239,720,679,1250,15,1189,401,225,1161,647,465,203,687,235,855,606,574,1293,1096,122,974,1234,328,608,922,810,193,1180,869,298,514,870,122,1129,851,1361,861,792,118,478,846,338,833,839,989,1235,1330,893,784,926,746,465,291,1223,364,1251,436,935,617,1133,851,479,601,517,989,279,1056,323,1429,1133,1199,1025,998,122,449,637,1122,410,1270,361,1285,895,115,1413,296,1190,1027,848,710,28,1113,1295,983,219,1228,1112,560,1203,335,159,1446,1358,1271,773,208,811,1336,590,857,574,1425,1441,660,1004,660,1308,66,259,837,1406,788,191,1046,652,1254,309,1340,1074,151,1176,1459,1070,1430,667,114,443,502,14,1206,1064,1418,775,484,1214,1459,1401,574,796,1233,440,447,38,1435,416,1477,1092,777,621,808,760,412,380,157,931,650,267,875,1471,358,722,1012,342,700,358,272,1299,72,684,412,1455,812,268,473,452,619,277,705,954,573,1535,457,27,1497,1063,669,732,632,548,1171,361,956,516,648,144,285,1030,333,1466,680,424,295,642,890,752,1581,89,132,174,1003,187,1063,1135,246,876,1361,52,1403,116,505,472,1288,1284,1457,1176,663,1524,299,881,263,725,1479,835,714,1270,488,369,1104,438,187,719,523,346,1514,26,542,456,101,1514,1136,1217,1372,488,1549,36,1519,389,193,1576,632,484,722,1066,1014,85,141,1329,1491,524,319,1027,1336,1068,150,288,640,621,426,327,494,116,1332,771,1309,1481,1316,197,1527,1418,267,376,1200,397,619,1060,802,841,630,1486,1666,871,1237,95,146,128,286,927,1167,1381,1081,1431,936,324,1673,144,73,1512,584,1048,288,643,685,391,271,1021,1365,27,926,1286,157,315,1007,310,542,14,1010,264,1441,1282,339,869,1035,11,401,702,1125,362,139,797,658,1661,707,1514,1267,64,220,892,365,1140,1236,1563,405,1173,396,795,110,1371,1725,1013,1026,680,884,1531,1009,1716,1719,101,1711,687,702,1027,1245,211,368,1518,1134,1621,1248,915,450,236,878,763,785,150,1102,1618,22,1410,1395,886,349,583,682,1548,1639,42,220,936,1150,1539,1292,850,1544,392,1784,772,1415,796,1750,1052,618,847,207,699,345,946,250,1521,735,427,1359,1061,494,1569,963,1598,560,800,1532,1687,3,1040,1800,1251,1320,1754,131,684,1765,1309,1168,1371,224,1385,465,1581,1309,445,1180,58,505,34,1065,603,256,103,788,912,1782,754,1312,111,390,853,299,1536,998,747,1537,64,1725,1854,1795,968,809,911,714,254,375,1121,1548,54,648,1150,1785,706,330,266,1274,1820,869,520,669,1392,238,1355,1470,129,636,1804,1130,1386,357,984,1257,1171,151,1762,537,773,1349,498,634,1356,332,295,1659,744,264,239,328,471,520,802,38,967,1534,623,1857,1720,1591,1019,729,586,113,860,154,1126,168,94,131,1418,1115,1355,643,215,1559,384,1366,646,728,204,1826,775,500,193,22,1725,504,1460,171,1337,1739,157,1174,965,1611,63,1097,554,1086,1742,536,949,389,1848,866,176,134,1025,285,1500,1780,525,345,1860,1218,954,30,1643,1602,1018,553,1399,1428,1947,615}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 836267973

35)

{0,1,0,0,2,2,1,4,8,9,5,8,5,11,14,6,8,6,8,17,18,3,12,18,8,21,17,20,7,15,19,28,5,5,23,8,29,19,1,12,37,19,20,35,19,7,29,15,31,42,38,10,5,14,19,13,36,36,54,23,18,46,13,54,6,58,51,65,39,56,21,27,25,21,26,8,21,63,64,44,7,81,57,80,53,41,49,75,49,43,78,43,68,68,8,11,56,20,44,72,6,71,47,25,51,6,34,81,9,21,47,111,47,31,38,103,81,20,37,31,40,67,51,94,100,4,89,122,109,59,33,13,81,7,113,42,4,60,110,111,102,101,30,91,72,41,127,56,124,13,115,77,139,100,119,48,90,5,65,72,139,99,13,163,160,88,15,58,168,147,2,28,24,95,22,33,51,177,154,164,69,130,55,136,4,102,29,1,139,0,44,119,9,71,47,74,90,20,101,29,0,167,170,85,147,152,197,95,7,170,186,93,125,183,113,116,196,180,179,170,196,97,49,153,54,32,159,87,89,25,207,188,65,96,62,154,166,87,230,82,55,143,166,67,126,83,50,26,46,219,175,8,62,247,37,242,3,120,78,136,158,6,19,12,159,157,14,263,238,269,57,259,182,264,187,217,81,272,139,47,243,4,132,127,92,216,151,271,148,155,159,277,77,56,136,61,288,115,103,29,14,283,18,156,210,153,48,71,59,266,71,209,113,138,41,206,196,4,137,129,13,167,169,89,134,204,186,249,140,185,5,162,230,252,74,125,3,203,233,100,160,279,96,103,70,42,283,207,174,74,74,259,181,248,16,59,58,167,116,96,295,342,232,100,312,116,48,33,190,28,217,157,337,193,224,40,35,122,193,39,82,356,197,239,374,60,206,222,267,62,342,202,282,357,159,99,155,269,181,317,209,328,95,303,7,250,224,15,293,81,248,152,298,1,151,0,309,335,257,332,365,143,51,4,138,224,222,100,388,88,148,405,9,238,9,20,132,158,421,117,102,86,237,348,266,332,39,63,100,382,372,220,299,35,269,168,80,1,366,240,420,316,127,398,342,50,167,460,69,253,302,110,445,114,167,15,408,142,204,358,462,206,474,397,393,49,208,50,160,136,488,235,299,106,460,486,271,92,105,41,240,222,303,257,250,14,14,327,23,237,195,305,14,137,249,340,264,420,119,107,459,143,175,131,496,217,469,271,396,238,82,253,214,500,379,308,255,208,423,366,505,161,90,144,450,318,444,41,191,307,193,405,119,59,480,322,82,87,123,199,202,263,481,5,353,53,292,549,84,35,262,469,215,118,62,379,564,503,414,58,74,340,259,128,129,548,464,322,304,276,462,164,298,267,166,510,541,431,221,179,400,239,400,134,93,579,413,513,459,187,182,123,467,190,504,274,182,496,502,330,367,375,50,552,212,384,229,247,209,272,338,63,567,284,42,339,243,292,432,148,411,254,513,154,379,584,80,156,13,610,341,466,511,96,471,537,184,645,577,520,418,220,258,301,301,48,90,57,531,230,634,599,230,342,306,143,552,283,48,325,630,407,62,387,92,649,527,100,545,575,421,199,425,34,44,112,316,70,234,526,405,536,64,253,349,200,607,585,455,390,26,14,641,109,269,270,598,711,467,682,603,16,1,88,538,331,249,241,361,94,582,198,150,268,599,297,632,126,336,29,236,707,582,589,37,591,523,402,598,56,83,72,409,9,347,339,432,352,7,348,691,18,472,188,572,756,15,13,478,257,616,321,44,1,610,707,191,705,774,701,573,335,710,668,166,413,410,247,8,392,536,782,438,751,447,391,87,362,145,529,606,488,510,464,425,435,220,145,112,214,649,579,573,608,431,800,377,731,777,553,612,95,420,470,278,584,380,642,364,242,173,749,700,207,703,232,76,828,5,117,710,100,446,667,353,626,235,594,27,551,733,47,326,105,632,160,393,786,382,276,645,412,53,323,663,625,175,627,707,214,631,109,350,560,756,454,317,589,702,872,614,373,202,841,209,698,90,429,864,54,716,531,34,414,868,850,198,294,756,691,647,333,724,839,780,26,89,471,488,760,343,167,787,229,606,577,57,187,600,631,830,341,726,695,259,569,902,909,771,353,903,553,395,697,897,169,403,112,70,85,573,619,438,722,30,666,233,254,417,769,560,579,6,655,192,471,420,550,419,580,903,454,795,138,590,757,361,296,895,697,755,370,715,793,598,353,511,455,604,396,201,176,235,414,85,37,761,247,451,373,490,655,278,902,448,410,13,833,888,389,745,66,274,57,156,637,914,103,921,486,125,797,310,963,31,261,617,53,786,419,210,28,83,50,492,1011,500,285,997,494,585,370,772,299,163,161,19,298,498,1022,328,962,771,671,607,730,339,232,107,707,462,765,204,171,191,744,1019,734,20,551,430,1017,344,592,642,142,737,467,340,1006,837,736,559,358,1067,1020,526,990,343,742,334,680,712,698,108,92,5,940,403,989,981,350,154,366,522,270,640,972,953,567,468,347,683,1058,29,668,548,567,473,329,888,481,363,109,447,493,179,782,810,542,683,714,964,17,778,609,557,166,939,551,56,905,388,48,853,869,649,702,59,364,286,525,769,821,295,7,893,938,287,593,1124,611,816,219,978,567,916,5,156,910,145,907,738,662,723,754,29,187,411,415,373,590,465,799,408,1122,1015,146,1062,112,605,1048,140,759,1061,685,525,870,1153,487,724,1144,12,303,737,66,1059,1127,403,686,872,251,6,1027,126,436,529,155,456,78,764,45,774,541,715,66,906,160,78,651,759,323,376,582,423,655,764,944,182,834,338,682,971,298,944,870,439,325,811,996,238,209,377,563,418,909,891,586,921,1084,133,1199,175,510,853,1196,193,1180,66,763,312,294,440,329,723,1028,808,1076,1245,73,477,805,980,1197,293,186,805,634,424,1060,961,1242,80,1021,696,235,1003,251,535,1086,386,24,950,211,388,435,1266,954,1224,521,834,1079,31,1126,117,783,1005,129,150,1291,4,557,44,143,228,742,1228,534,206,348,670,802,351,1188,256,1287,1225,195,612,524,576,1228,303,277,569,753,578,696,291,243,1156,1178,1070,937,1228,382,845,123,145,978,154,224,924,635,1229,0,307,166,460,715,683,1223,1163,943,958,490,199,1134,856,706,95,252,786,788,154,86,294,1110,224,900,86,170,986,320,1258,115,1111,86,977,845,164,1273,70,388,416,1280,357,436,829,834,52,589,802,485,452,1161,524,1162,255,1199,922,1127,1099,292,5,607,1019,1323,174,1137,1138,133,1337,870,1359,424,1362,87,1333,132,968,1062,1233,688,56,16,1092,1236,822,331,630,219,1337,812,319,949,850,29,146,529,33,940,108,624,1194,476,115,413,1368,920,121,1156,452,1,972,672,1334,319,1368,430,1192,1424,13,862,1187,1410,434,827,665,503,565,114,1029,1103,1097,1199,736,383,863,448,495,875,1016,713,1037,1141,98,824,678,1456,676,507,209,1288,858,845,757,477,690,1062,550,120,1442,817,1402,585,748,259,35,1133,1112,507,1313,288,1060,131,661,598,255,932,539,640,373,1381,721,1109,1055,1295,770,1265,1235,627,558,582,613,774,1252,929,971,1030,1174,10,260,350,1170,622,905,1408,330,929,378,231,206,904,494,827,1259,1217,447,1348,1016,1498,1194,1234,512,1412,861,463,45,385,481,976,758,416,1083,968,384,245,900,866,1072,1480,43,1007,801,451,407,898,1050,433,380,572,1404,1022,728,662,1200,575,793,532,117,139,1352,1528,1191,142,545,1382,239,1282,494,1511,614,1370,757,1511,28,1374,1134,456,1475,1091,750,1420,653,329,660,250,942,862,638,764,766,522,755,1604,1322,446,995,170,678,1534,1189,176,1135,1311,422,54,1604,273,237,622,623,497,282,1075,296,1570,1032,327,1218,968,464,1244,967,215,783,1284,1010,1673,1339,785,1297,1173,257,76,826,345,1261,1349,1025,432,1420,1005,871,274,924,896,1661,873,1640,828,1520,157,1282,1319,1566,712,765,874,1200,966,141,1372,1300,999,1558,905,694,643,1337,692,1608,1156,835,979,1150,593,18,410,362,803,854,540,703,700,521,1205,1267,81,1276,152,723,1137,550,237,1400,1101,1730,51,705,663,861,1363,109,1162,642,293,1619,692,894,1335,1365,658,1673,334,1764,233,1571,1593,1616,221,892,958,1067,1015,1492,487,1588,385,806,1540,557,1366,716,83,65,1388,1113,385,699,1647,1733,984,1621,1212,375,1453,316,117,107,1714,1673,708,184,968,61,1341,187,375,1693,925,622,1522,6,589,1307,550,821,1612,1464,1234,1197,1441,221,1082,112,1688,475,401,32,1218,1573,955,880,1763,379,95,36,1348,1084,232,670,18,1422,835,1404,1341,614,438,1366,1815,1202,5,939,553,399,1764,603,861,886,624,1389,1601,431,451,1388,451,974,1608,803,358,1626,165,1104,124,264,226,1328,37,1290,732,160,504,657,484,1827,1268,1211,983,927,979,6,1707,1806,1311,1172,777,619,1622,1225,1434,22,586,335,655,967,609,747,1458,991,312,831,912,806,1521,1262,1727,1296,1187,1714,1712,254,1031,905,1346,1503,1099,1352,1011,1757,244,1856,915,1195,794,54,1431,1801,1773,843,339,770,1867,1744,1390,900,715,735,1452,411,382,730,1862,442,1045,572,897,1517,650,1200,1057,1286,942,659,341,1669,207,1559,1321,464,1759,393,1363,239,1367,1364,974,589,1491,1552,74,512,722,481,1240,1763,147,168,357,132,1176,815,1663,698,1351,1799,1669}
{1210,5846,3420,1331,7295,7463,2380,2270,5605,3930,8085,7751,9723,53,5519,585,1937,2297,5431,2466,9369,2767,7151,7556,8952,4077,3813,8060,8032,9841,4606,7796,9338,1703,8998,951,5315,7217,7276,9258,3416,6526,5868,5233,1953,4627,6842,9166,9493,3146,2323,2847,4895,5433,4976,824,7709,1402,3453,31,1313,9205,2418,9735,6884,5227,5539,5280,4382,9155,8742,8829,9732,791,5261,6844,7089,2541,8958,7866,5595,1859,8022,490,2047,5462,796,873,9241,6326,1141,4524,5296,3354,6588,5515,196,9019,1100,4875,7702,1088,9188,1441,739,2884,9987,4714,1707,5314,9413,4135,8404,4918,8232,5860,5922,2420,623,8289,2028,1101,927,6630,5083,1969,9478,7945,5382,9843,2017,2580,7756,1890,1054,5154,3086,7062,8300,2264,3438,9200,9582,5226,1900,7051,5124,9939,6303,232,5314,3901,5560,3717,6601,4135,94,3312,3204,358,3103,8535,8439,2090,366,1546,9498,917,4070,520,6477,7971,6653,43,5420,6867,1852,8114,9954,8745,295,3832,1406,9570,6313,8787,194,3455,8174,1217,8708,3461,9838,8629,3936,178,3684,3985,4431,4024,8717,6456,497,2190,8491,6747,7479,3777,4153,8875,539,5137,3471,4715,5474,8600,2349,6386,1414,2413,4042,6957,6142,811,5010,3249,6190,776,6146,1759,8557,7728,184,5362,5865,2845,2530,5834,8046,870,3690,3139,1712,2013,8925,7660,7992,9496,9133,2729,3681,326,286,3216,9862,2469,5147,8063,9404,2784,7017,9101,8418,3751,9046,896,152,8586,8055,35,4494,3581,4682,5581,7478,8675,2605,6531,6143,1441,3114,4781,3929,6982,7747,8493,3245,7759,1374,5174,974,7596,8293,2660,2477,9215,6167,3021,1769,9567,7507,4768,9842,2737,3767,9561,4616,6212,503,1275,5136,3165,5674,6064,4203,8590,822,6197,1215,2616,5772,9097,6932,3243,4631,9464,497,951,3281,6531,4963,6067,1436,4702,4337,7138,4812,1209,7816,3992,6954,4702,3620,8466,7762,9888,3472,1998,9495,4309,1161,8538,725,1068,924,6628,7689,2951,3810,7540,9370,803,658,276,8928,7493,3390,9125,5422,8514,3417,614,2791,1124,8321,6228,944,4198,2789,3046,7680,510,270,8454,353,352,6,1190,7572,9123,6969,9534,5773,2464,4177,5851,8001,3576,7039,5266,942,5831,5928,4950,9079,5779,283,3172,2169,4788,1891,1630,9146,7337,1968,9117,8769,1982,6672,4839,3365,6298,1352,9208,3845,8899,4972,4349,7139,8153,4326,5756,9649,2900,7891,9480,4979,7730,6685,9040,5836,5683,2592,5552,8006,1565,4520,2998,2687,649,8758,1075,7492,8468,3371,3397,3306,4820,5216,2047,7423,3420,5535,2042,1711,7047,7259,748,6485,200,4908,9396,9600,7930,1497,2956,4123,6139,8987,9048,9536,6102,1797,2063,394,2985,3832,6022,7901,7177,4509,6758,8768,9926,1825,4167,9433,8269,9525,2731,8957,5932,1889,1186,5653,9829,3280,3693,1019,8617,2818,9503,4562,2544,397,2804,8561,5550,9759,6367,2164,9955,5227,7871,4296,9058,8474,8482,3072,6464,4592,4774,2820,4360,9969,7169,50,5634,4011,2525,1879,2184,665,1664,347,7195,7304,7929,9229,3695,3287,9213,8868,9043,4768,4097,1343,8752,6618,500,486,8376,5399,3502,2042,4070,4443,7566,6712,9967,9999,4779,549,6557,6677,7266,9236,3524,8804,6151,5430,9094,3129,4406,8787,1983,616,3394,5481,1448,6245,9611,4054,9949,1873,8980,415,6472,2286,9347,4355,4226,1544,8669,9348,1395,7414,6243,6950,5854,9931,6614,775,6390,6227,6449,4400,6618,9100,1012,6548,9422,7531,8232,4478,8692,378,1831,3398,1374,9495,1569,3831,3747,4619,7486,2027,3516,4315,3219,2446,8676,9416,4857,4845,7468,9792,5368,6770,5838,234,8280,3406,8835,527,1055,6249,6867,8799,2385,3399,752,7123,8804,4776,8983,1628,7201,2600,5572,9851,8436,6895,2690,6071,2917,3490,8146,187,1926,8411,6351,3336,7234,6591,6604,3363,7800,5385,2141,3030,1294,8804,6115,5699,3707,1226,1665,1548,9270,3517,3337,8940,9071,9610,4765,1024,8269,8380,9648,7510,178,8179,7935,5422,5119,9228,631,6408,2205,4637,6050,205,4449,7679,3927,2692,2393,4983,5876,5996,2137,8564,6123,3744,6591,5027,1234,5539,4147,3833,8651,6751,9365,40,1642,6305,8533,6206,9302,4236,2806,5519,2996,8697,8442,2506,7764,2298,2246,4507,5384,1799,3134,3854,3210,2092,2326,5063,5269,8840,9911,9078,3382,8287,7596,6518,3064,7427,4025,9956,270,3421,9913,1419,7780,352,7866,3193,8852,538,9045,8026,1066,7701,9260,6825,4117,5557,6853,9978,6712,9964,102,816,8536,4707,2905,2233,2949,467,8271,4088,7135,4496,166,2178,3467,63,7110,7451,9142,7269,503,9566,92,8646,2775,1036,8983,9099,1138,4652,9250,4308,5028,333,3078,2572,3006,3591,9058,9717,6130,428,7392,3279,4,7360,8956,3309,1597,8568,6975,4909,7425,5779,9630,3734,7397,978,2985,8105,4533,5988,6560,4357,4645,263,5172,6664,5504,374,1654,5575,6456,7777,6344,4584,9331,4517,8445,3224,8638,8578,4730,6608,2495,8695,1865,55,216,373,2727,642,8006,3691,1718,9593,5275,2056,9313,2831,9271,8228,146,5480,9430,9889,671,9433,8559,6427,8453,6305,1453,8871,4438,7296,7538,944,7754,862,778,7954,6829,7334,541,561,3351,1946,2391,8343,1081,3170,7953,1666,1439,5917,3484,9038,9214,2246,9336,3960,9171,6620,5653,2671,5757,7655,6596,5655,2517,1447,3395,3560,413,3542,2324,475,6990,6484,5871,5117,8260,1217,3673,9256,8795,8603,8607,852,8244,9913,6327,8848,2781,2535,3634,6710,4996,9813,1450,7855,1871,8683,9451,975,4374,3950,4815,2243,3087,3663,1927,4005,3823,2364,51,8493,2779,2212,4134,4926,1249,1839,8893,4636,2241,1543,5168,3325,7918,8382,4628,1740,6152,8230,3668,6438,6493,3552,1929,8030,5737,5427,235,1250,1866,6680,9444,8633,4904,2811,1810,4132,6621,3783,8547,3459,9319,3266,8668,2799,7844,8690,3773,4490,9969,7929,9734,4491,8406,6271,9193,5571,8114,5973,5784,2325,3037,3543,1017,9197,7254,3114,8299,5885,6100,3400,5619,8882,5777,8292,8395,8025,2334,1783,28,7764,6257,7928,6631,4143,9770,3378,2753,7935,3270,597,9694,6402,2211,7525,5739,543,3640,8745,6897,4792,176,779,3752,6621,3125,9516,7043,2835,4468,5810,5501,2896,2429,2389,2605,3830,6438,3469,8359,1537,3874,9728,5655,3581,861,5301,5959,9674,8654,7346,9634,5390,9374,509,2100,8591,9785,1955,4296,3238,8334,1277,4435,1766,7338,8292,2377,9694,1159,277,7012,350,244,2331,8768,9075,1615,6926,4482,9253,2515,5828,9289,7701,8663,68,5900,840,9254,8732,2115,5924,3151,4648,2281,1443,7649,3070,3682,6443,1498,9501,1743,9642,4972,8221,4186,3985,4328,718,3407,2709,8693,9531,4091,8255,1211,7392,5192,6543,7765,9080,90,7009,1625,7216,7984,7869,611,4248,7667,7726,1879,8110,4424,1202,1067,1471,2638,5422,6882,5062,2555,9765,4850,2176,1931,2248,8402,9742,1236,2628,8478,6111,1207,9683,5334,647,5355,2231,8300,3961,5296,324,9154,6459,1788,8054,691,2630,696,4878,7092,4988,6583,4888,9890,9225,501,1832,772,4879,7595,5136,917,511,2102,518,1936,214,2962,4806,2679,4318,7399,8243,6068,3566,7200,6136,2933,8089,280,1216,8797,8640,5011,2793,6042,8964,1860,8025,3662,3029,9033,6970,6492,5619,2704,9964,172,5086,9519,6164,7091,2235,4629,9485,8623,3896,6444,4773,974,4544,5268,3000,9929,5038,3928,1692,2096,6478,8996,457,15,4832,3838,1039,6384,3211,8359,7611,5898,3274,4173,4509,5895,1893,9745,3276,8465,2460,6077,2868,9617,6760,3558,9150,772,8033,2038,6575,7254,3728,8927,4622,7998,351,2190,5903,8058,2802,1440,1190,5007,8795,7051,7996,4918,1717,2490,6306,1495,8011,1867,6543,8071,14,4884,9104,6669,799,2648,3627,5467,453,7459,9019,6594,8800,2932,191,5389,9043,6394,4183,3781,5742,1588,2782,7297,7978,9536,6038,6161,2065,8243,8302,2504,9162,6176,6677,4630,5224,4409,479,9391,7278,2292,2116,5652,2913,8107,7987,4621,2183,4990,3323,7890,7823,7453,967,8782,981,6921,8744,7817,7608,7313,174,5853,8647,5091,2064,1484,4246,675,5586,3982,4125,1312,8563,9961,7483,5527,4900,1487,7142,9341,707,400,6823,8195,1614,3268,2448,5934,8176,7656,6849,6165,2278,1822,1817,7744,9758,8674,3392,1559,2280,8020,271,9187,1490,553,8682,2241,2675,7760,6602,8823,9651,6136,8599,3091,3339,445,8118,412,5950,5873,849,4182,4050,7857,6586,9767,2787,5255,1771,4891,2495,654,2577,7271,220,4082,2018,9856,8352,2050,6437,8367,6792,6732,8667,8758,1051,181,3678,1250,368,8741,7640,4084,9057,2344,1821,5410,9375,1854,7111,6232,4625,9194,9434,3480,6762,665,9128,6721,3989,1426,1582,9229,8636,687,1808,1786,9107,6154,961,6418,358,1467,1672,3134,5973,5727,7443,8778,5745,524,6733,5848,3155,2841,5806,908,5345,1874,5783,241,3344,252,648,5095,9864,7041,409,7764,4333,60,4391,7664,624,7735,1412,1878,2602,3661,309,6258,7515,47,3452,450,7685,1154,6146,6337,3709,7622,6667,2904,906,1346,1803,104,4556,403,6213,9970,565,7346,8403,183,4019,1396,6111,940,2684,2229,939,1504,6229,8164,6806,6062,460,3725,8779,9703,1165,8602,6234,1241,2450,7895,4178,2267,9490,9783,440,8068,6171,6405,8007,139,5492,771,1254,4620,2021,8989,4168,6971,8434,5332,7983,548,1356,8798,9456,2480,3291,4682,8999,3120,8096,6805,832,5732,8686,2824,7624,3928,4495,1345,8010,7707,9737,5172,715,4676,6963,1512,4515,6138,1912,7223,1269,6485,2088,8213,4060,6695,242,9475,8229,6421,3809,4131,796,6488,3218,656,1664,7380,3589,7078,8719,7249,2781,2802,817,703,3855,1379,2547,4860,1256,7814,2866,3856,3837,1453,9869,6966,8366,6359,9488,9793,1706,1646,3242,436,904,1412,8267,8010,9535,2985,9029,1006,9425,7322,7704,103,5046,9919,4528,191,4274,5250,6944,5464,4447,4859,3942,7938,9312,6496,3699,4855,2485,5191,9720,3086,106,5823,2861,8887,4058,8949,2529,6391,3472,2992,1455,4962,8959,6485,8229,1465,2787,2534,7818,4361,7892,5983,7787,1918,8086,7361,171,6249,723,2447,2724,4995,1267,6710,5091,4343,2692,1642,445,4535,7696,5,5233,3137,6317,3552,7584,9030,2461,7222,2269,2512,7089,2836,5581,304,7142,5176,5867,9229,9374,7220,5556,517,4144,95,9462,2057,7031,5056,1031,6339,9761,5630,2072,177,7165,7578,8919,3054,4329,7928,5753,4958,1555,7592,2529,8705,8768,8736,4774,5304,7306,4714,9990,1153,135,8492,3205,7560,9806,2270,413,7841,4612,6481,408,7864,3058,7732,3833,3369,9125,4378,6566,4099,8349,6774,9042,1308,98,1171,8746,418,232,2060,8589,2013,9410,7168,2849,5273,2025,6326,9461,9028,264,667,1345,6252,1755,7062,278,2482,3362,3007,7702,9690,2587,4914,172,5953,46,5408,3262,8135,8184,5046,2064,570,1432,6738,1197,2147,6060,8950,2962,7590,5761,7203,6455,1535,3723,6077,1835,685,1964,7237,4522,9859,8344,9276,4102,7455,3939,7071,8571,9739,9397,2669,7315,7621,9706,6498,5765,3155,4703,355,6450,2354,6011,5124,1631,1377,1788,9210,3172,3777,4192,6470,9652,4515,9872,2419,3580,3241,6647,3376}
Returns: 784602497

Submissions are judged against all 52 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MapleTree with a public method int sum(vector<int> p, vector<int> length) · 52 test cases · 2 s / 256 MB per case