题解思路

这是一道典型的DFS遍历结合动态维护的树上路径问题，核心在于通过路径的增量计算和双向统计策略，高效求解所有可能路径的逆序对最大值。

核心算法分析

问题本质理解： 题目要求在树上找一条简单路径，使得路径上节点值构成的序列逆序对数量最大。关键洞察是：我们需要遍历所有可能的路径，并动态维护逆序对计数。

关键算法洞察：

路径表示： 树上的任意简单路径都可以唯一地表示为：从某个节点开始，沿着树的边进行DFS遍历得到的节点序列。

逆序对计算策略： 对于路径上的每个新加入节点，我们需要计算：

1. 该节点与之前路径上所有节点形成的逆序对数量
2. 该节点与之前路径上所有节点形成的顺序对数量

双向统计技巧：

// 对于新加入的节点值currentValue
int newInversions = 0;
int newNormalPairs = 0;

for (int previousValue : pathValues) {
    if (previousValue > currentValue) {
        newInversions++; // 形成逆序对
    } else if (previousValue < currentValue) {
        newNormalPairs++; // 形成顺序对
    }
    // previousValue == currentValue 不影响逆序对计数
}

状态转移设计：

// 更新路径状态
int updatedInversions = currentInversions + newInversions;
int updatedNormalPairs = currentNormalPairs + newNormalPairs;

// 考虑路径反向的情况（重要优化）
maxInversions = Math.max(maxInversions, 
                        Math.max(updatedInversions, updatedNormalPairs));

路径反向处理： 由于树上路径可以从任一端点开始遍历，我们需要同时考虑正向和反向路径的逆序对数量。反向路径的逆序对数量等于正向路径的顺序对数量。

详细算法设计

DFS遍历框架：

private void exploreTreePaths(int currentNode, int parentNode, 
                            List<Integer> pathValues, 
                            int forwardInversions, int forwardNormalPairs) {
    
    int nodeValue = nodeValues[currentNode - 1];
    
    // 计算新节点带来的贡献
    int additionalInversions = 0;
    int additionalNormalPairs = 0;
    
    for (int pathValue : pathValues) {
        if (pathValue > nodeValue) {
            additionalInversions++;
        } else if (pathValue < nodeValue) {
            additionalNormalPairs++;
        }
    }
    
    // 更新路径统计
    int totalInversions = forwardInversions + additionalInversions;
    int totalNormalPairs = forwardNormalPairs + additionalNormalPairs;
    
    // 更新全局最大值（考虑正反两个方向）
    if (!pathValues.isEmpty()) { // 确保路径至少包含一条边
        globalMaxInversions = Math.max(globalMaxInversions, 
                                     Math.max(totalInversions, totalNormalPairs));
    }
    
    // 继续向子节点扩展
    List<Integer> extendedPath = new ArrayList<>(pathValues);
    extendedPath.add(nodeValue);
    
    for (int childNode : adjacencyList[currentNode]) {
        if (childNode != parentNode) {
            exploreTreePaths(childNode, currentNode, extendedPath, 
                           totalInversions, totalNormalPairs);
        }
    }
}

完整搜索策略：

// 从每个节点作为起点开始搜索
for (int startNode = 1; startNode <= n; startNode++) {
    exploreTreePaths(startNode, startNode, new ArrayList<>(), 0, 0);
}

复杂度分析：

• 路径数量：O(n²)（树上简单路径数量的上界）
• 单路径处理：O(n)（路径长度最大为n）
• 总体复杂度：O(n³)
• 空间复杂度：O(n)（递归栈和路径存储）

Java代码实现

import java.io.*;
import java.util.*;

public class Main {
    
    private static int globalMaximumInversions;
    private static int[] nodeValues;
    private static List<Integer>[] treeAdjacencyList;
    
    @SuppressWarnings("unchecked")
    private static void buildAdjacencyList(int n, int[] parentArray) {
        treeAdjacencyList = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            treeAdjacencyList[i] = new ArrayList<>();
        }
        
        // 根据父子关系构建双向邻接表
        for (int child = 2; child <= n; child++) {
            int parent = parentArray[child - 2];
            treeAdjacencyList[parent].add(child);
            treeAdjacencyList[child].add(parent);
        }
    }
    
    private static void searchOptimalPath(int currentVertex, int parentVertex, 
                                        List<Integer> currentPath, 
                                        int accumulatedInversions, 
                                        int accumulatedNormalOrders) {
        
        int vertexValue = nodeValues[currentVertex - 1];
        
        // 计算当前节点与路径中已有节点的关系
        int newInversionCount = 0;
        int newNormalOrderCount = 0;
        
        for (int existingValue : currentPath) {
            if (existingValue > vertexValue) {
                newInversionCount++;
            } else if (existingValue < vertexValue) {
                newNormalOrderCount++;
            }
        }
        
        // 更新累积统计
        int totalInversions = accumulatedInversions + newInversionCount;
        int totalNormalOrders = accumulatedNormalOrders + newNormalOrderCount;
        
        // 更新全局最优解（考虑路径的正反两个方向）
        if (!currentPath.isEmpty()) {
            globalMaximumInversions = Math.max(globalMaximumInversions, 
                                             Math.max(totalInversions, totalNormalOrders));
        }
        
        // 扩展路径继续搜索
        List<Integer> extendedPath = new ArrayList<>(currentPath);
        extendedPath.add(vertexValue);
        
        for (int adjacentVertex : treeAdjacencyList[currentVertex]) {
            if (adjacentVertex != parentVertex) {
                searchOptimalPath(adjacentVertex, currentVertex, extendedPath, 
                                totalInversions, totalNormalOrders);
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader inputReader = new BufferedReader(new InputStreamReader(System.in));
        
        int treeSize = Integer.parseInt(inputReader.readLine());
        
        String[] valueInputs = inputReader.readLine().split(" ");
        nodeValues = new int[treeSize];
        for (int i = 0; i < treeSize; i++) {
            nodeValues[i] = Integer.parseInt(valueInputs[i]);
        }
        
        int[] parentRelations = new int[treeSize - 1];
        if (treeSize > 1) {
            String[] parentInputs = inputReader.readLine().split(" ");
            for (int i = 0; i < treeSize - 1; i++) {
                parentRelations[i] = Integer.parseInt(parentInputs[i]);
            }
        }
        
        buildAdjacencyList(treeSize, parentRelations);
        
        globalMaximumInversions = 0;
        
        // 从每个节点开始进行路径搜索
        for (int startVertex = 1; startVertex <= treeSize; startVertex++) {
            searchOptimalPath(startVertex, startVertex, new ArrayList<>(), 0, 0);
        }
        
        System.out.println(globalMaximumInversions);
        inputReader.close();
    }
}

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class TreePathInversionCalculator {
private:
    int maxInversionCount;
    vector<int> vertexValues;
    vector<vector<int>> graphAdjacency;
    
    void performDepthFirstSearch(int currentNode, int previousNode, 
                               vector<int>& pathSequence, 
                               int forwardInversions, int forwardRegularPairs) {
        
        int nodeVal = vertexValues[currentNode - 1];
        
        // 统计新节点与现有路径的关系
        int inversionIncrement = 0;
        int regularPairIncrement = 0;
        
        for (int pathVal : pathSequence) {
            if (pathVal > nodeVal) {
                inversionIncrement++;
            } else if (pathVal < nodeVal) {
                regularPairIncrement++;
            }
        }
        
        // 累加到总计数
        int totalInversions = forwardInversions + inversionIncrement;
        int totalRegularPairs = forwardRegularPairs + regularPairIncrement;
        
        // 更新全局最优解（路径正反向都考虑）
        if (!pathSequence.empty()) {
            maxInversionCount = max({maxInversionCount, totalInversions, totalRegularPairs});
        }
        
        // 路径扩展
        pathSequence.push_back(nodeVal);
        
        // 递归遍历相邻节点
        for (int neighborNode : graphAdjacency[currentNode]) {
            if (neighborNode != previousNode) {
                performDepthFirstSearch(neighborNode, currentNode, pathSequence, 
                                      totalInversions, totalRegularPairs);
            }
        }
        
        // 回溯
        pathSequence.pop_back();
    }
    
public:
    int solve(int n, const vector<int>& values, const vector<int>& parents) {
        maxInversionCount = 0;
        vertexValues = values;
        graphAdjacency.assign(n + 1, vector<int>());
        
        // 构建邻接表
        for (int i = 0; i < parents.size(); i++) {
            int child = i + 2;  // 子节点编号从2开始
            int parent = parents[i];
            graphAdjacency[parent].push_back(child);
            graphAdjacency[child].push_back(parent);
        }
        
        // 从每个节点作为路径起点进行搜索
        for (int startNode = 1; startNode <= n; startNode++) {
            vector<int> emptyPath;
            performDepthFirstSearch(startNode, startNode, emptyPath, 0, 0);
        }
        
        return maxInversionCount;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int nodeCount;
    cin >> nodeCount;
    
    vector<int> nodeValues(nodeCount);
    for (int i = 0; i < nodeCount; i++) {
        cin >> nodeValues[i];
    }
    
    vector<int> parentArray;
    if (nodeCount > 1) {
        parentArray.resize(nodeCount - 1);
        for (int i = 0; i < nodeCount - 1; i++) {
            cin >> parentArray[i];
        }
    }
    
    TreePathInversionCalculator calculator;
    int result = calculator.solve(nodeCount, nodeValues, parentArray);
    
    cout << result << endl;
    
    return 0;
}

时间复杂度：O(n³)，遍历所有路径O(n²) × 每路径计算O(n) 空间复杂度：O(n)，递归栈深度和路径存储