思路分析

这个问题的核心是找到一条能使路径值序列的逆序对数量最大化的简单路径。

路径与逆序对：树中的任意两个节点 $u$ 和 $v$ 之间都存在一条唯一的简单路径。对于一条路径，我们可以从 $u$ 走到 $v$ ，也可以从 $v$ 走到 $u$ ，这会产生两个方向相反的序列。假设从 $u \to v$ 的序列是 $B$ ，那么从 $v \to u$ 的序列就是 $B$ 的逆序。一个序列的逆序对数量和其反转序列的非逆序对（即满足 $i<j$ 且 $B_i < B_j$ 的配对）数量是相同的。因此，我们对于一条确定的路径（无向），需要计算两个方向的逆序对数量，并取其中的较大值。
暴力枚举：最直接的想法是枚举所有的简单路径。一条简单路径由其起点和终点唯一确定。我们可以枚举所有 $O(n^2)$ 个节点对 $(u, v)$ 作为路径的端点。对于每一对 $(u, v)$ ，我们找出它们之间的路径（例如使用BFS或DFS，时间 $O(n)$ ），然后计算路径序列的逆序对数量（暴力计算为 $O(n^2)$ ，使用归并排序或树状数组为 $O(n \log n)$ ）。这样总复杂度至少为 $O(n^2 \cdot n \cdot n) = O(n^4)$ ，对于 $n=300$ 来说太慢了。
优化思路 - 固定起点：我们可以优化这个过程。与其枚举路径的两个端点，不如枚举路径的一个端点，然后通过遍历找到所有以它为起点的路径。

P3692.第3题-树上逆序对

1000ms

Difficulty: 6

所属公司 : 得物

算法与标签>DFS

小红给小红画了一颗 $n$ 个节点的数，这棵树的每个节点上都有一个值 $a_i$ 。现在小红想要小红回答以下问题：

在树上选择一条简单路径（每个点经过最多一次），并将沿途经过的点的值按顺序写下来（包括起点与终点），之后得到一个序列 $B$ ，并计算这个序列的逆序对个数。小红想知道能够选择的所有路径中逆序对数量最多是多少。

$(i,j)$ 是逆序对当且仅当 $i＜j，B_i＞B_j$ 。

第一行一个正整数 $n$ ；

接下来一行 $n$ 个正整数 $a_i$ ，表示节点 $i$ 的值；

接下来一行 $n-1$ 个正整数 $p_i(2≤i≤n，1≤p_i<i)$ ，表示节点 $i$ 与 $p_i$ 之间有一条边。

$1≤n≤300, 1≤a_i≤10^5$

输出一个整数，表示逆序对最多的数量。

输入

5
1 2 3 4 5
1 2 2 4

输出

说明

选择的路径为 $5$ $4$ $2$ $1$ ，共 $6$ 个逆序对。

输入

预期输出（选填）