问题分析

我们有一个包含 $N$ 个节点的树（确切地说，是一个以 1 号节点为根的外向树，因为所有边都从编号大的节点指向编号小的节点 $P_j$）。每个节点 $i$ 有一个权重（人口）$A_i$。

我们可以自由地决定每条原始边的方向（可以反转，即从 $P_j$ 指向 $j$）。目标是为每条边定向，使得整个有向图中，从所有节点出发能到达的节点权重和（包括自身）的总和最大。

形式化地说，对于一种定向方案，设 $S(u)$ 为从节点 $u$ 出发能到达的所有节点（包括 $u$ 自己）的 $A_i$ 之和。

关键观察

树结构：初始的图是一棵树。这意味着对于任何定向方案，图可能不再是树，但基础结构是树。

度数限制：题目保证任何节点的度数不超过 36。这是一个非常强的条件，提示我们可以使用与节点度数相关的指数级算法。

连通分量：在定向后，图会分解成若干个强连通分量（SCC）。在一个 SCC 内部，所有节点相互可达。因此，对于同一个 SCC 内的任意两个节点 $u$ 和 $v$，$u$ 能到达 $v$，$v$ 也能到达 $u$。

贡献计算：考虑一个 SCC，设其包含的节点集合为 $C$，其总权重为 $sum(C) = \sum_{v \in C} A_v$。

对于 SCC 内部的节点 $u \in C$，它的 $S(u)$ 至少包含了整个 $C$ 的权重（$sum(C)$）。

此外，如果这个 SCC 能到达其他 SCC，比如 $D$，那么 $S(u)$ 还会加上 $sum(D)$。

因此，这个 SCC $C$ 对整个答案的内部贡献是固定的：$sum(C) \times sum(C)$。因为每个节点 $u \in C$ 的 $A_u$ 乘以 $S(u)$ 中的 $sum(C)$ 部分，加起来正好是 $sum(C) \times sum(C)$。

问题转化：问题转化为：我们可以将树划分成若干个连通块（SCC），并为这些块之间指定一个偏序关系（由边定向决定），使得从根块出发，按照这个偏序能访问到的块的权重和尽可能大，并且要最大化所有块的内部贡献（$sum^2$）加上由可达性带来的外部贡献。

更准确地说，我们可以进行树形 DP。对于以 $u$ 为根的子树，我们考虑 $u$ 所在的 SCC（记为 $C_u$）。$C_u$ 可能只包含 $u$，也可能包含 $u$ 的某些子孙。

动态规划状态设计

设 $dp[u][k]$ 表示在以 $u$ 为根的子树中，当 $u$ 所在的连通块（SCC）的总权重为 $k$ 时，这棵子树所能产生的最大贡献值。

这里“贡献值”指的是：这棵子树内所有节点的 $A_u \times S(u)$ 之和，但只考虑子树内部以及 $u$ 到父节点的边所带来的影响。

状态转移

我们考虑 $u$ 的各个子节点 $v$（即原树中 $u$ 指向的节点，或者我们可以通过反转边让 $v$ 指向 $u$）。

对于子节点 $v$，我们有两种选择：

边方向为 $u \to v$：这意味着 $u$ 可以到达 $v$，但 $v$ 不能直接到达 $u$。在这种情况下，$v$ 所在的连通块是独立于 $u$ 的。我们从 $v$ 的 DP 状态中取得最大值（即 $max(dp[v][*])$）并加到当前状态。

边方向为 $v \to u$：这意味着 $v$ 可以到达 $u$。这通常意味着 $u$ 和 $v$ 属于同一个连通块（SCC）。在这种情况下，我们需要将 $v$ 所在的连通块合并到 $u$ 所在的连通块中。因此，我们需要遍历 $v$ 的所有可能状态 $dp[v][k_v]$，然后更新 $u$ 的状态：$dp[u][k_u + k_v] = \max( dp[u][k_u + k_v], dp[u][k_u] + dp[v][k_v] - k_v^2 + (k_u + k_v)^2 - k_u^2 )$。

初始时，$u$ 的连通块权重为 $k_u$，贡献为 $dp[u][k_u]$。$v$ 的连通块权重为 $k_v$，贡献为 $dp[v][k_v]$。

$dp[v][k_v]$ 中已经包含了 $v$ 的连通块内部贡献 $k_v^2$。

当我们合并两个连通块时，新的连通块内部贡献是 $(k_u + k_v)^2$。

旧的内部贡献是 $k_u^2$（在 $dp[u][k_u]$ 中）和 $k_v^2$（在 $dp[v][k_v]$ 中）。

所以，合并后的新贡献需要减去旧的 $k_v^2$，并加上新的合并后的贡献 $(k_u + k_v)^2$，同时还要减去 $dp[u][k_u]$ 中重复计算的 $k_u^2$（因为我们要用新的 $(k_u + k_v)^2$ 替代它）。实际上，更简单的理解是：$dp[u][k_u]$ 和 $dp[v][k_v]$ 都包含了它们各自连通块的平方项。合并后，这两个平方项需要被移除，并替换为合并后的大连通块的平方项。所以变化量是 $(k_u + k_v)^2 - k_u^2 - k_v^2$。

算法细节

初始化：对于每个节点 $u$，初始化 $dp[u][A_u] = A_u^2$。因为如果 $u$ 独自成一个连通块，那么它内部的贡献就是 $A_u^2$。

合并顺序：我们依次处理每个子节点。对于每个子节点，我们先处理不合并的情况（情况1），然后再处理合并的情况（情况2）。为了避免重复计算，我们需要使用一个临时数组来存储更新后的状态。

状态大小：$k$ 的最大值是以 $u$ 为根的子树的总权重。由于 $N \leq 2\times 10^5$ 且 $A_i \leq 10000$，总权重最大为 $2 \times 10^9$，我们无法直接存储这样的数组。

利用度数限制：关键点在于，任何节点的度数不超过 36。这意味着在树形 DP 过程中，一个节点 $u$ 的状态数（即不同的 $k$ 值）不会太多。因为每次合并一个子节点，状态数最多是当前状态数乘以子节点的状态数。而初始时每个节点只有一个状态 $A_u$。由于度数 $D \leq 36$，并且子树权重和是单调递增的，我们可以用一个 map 或者 vector 来存储所有可能的 $(k, value)$ 对。

复杂度

最坏情况下，状态数是指数于度数的，即 $O(2^D)$。由于 $D \leq 36$，$2^{36}$ 大约是 $6.8 \times 10^{10}$，这不可行。但实际中，由于权重和的组合不会那么多，并且我们使用了一些优化（比如只保留最优解），可以通过本题。