CSC3100 Assignment3[已完成]

发表于 2023-12-19 更新于 2025-01-09

这里是CSC3100 Assignment3的笔记，希望对你有帮助！
有关树型动态规划&红黑树
1 Node Distance
1.1 Description
You are given a tree with $n$ nodes, where each edge in the tree has a corresponding weight denoting the
length of each edge. The nodes in the tree are colored either black or white. Your task is to calculate the sum of distances between every pair of black nodes in the tree. Let $B={b_1,b_2,…}$ a set of black nodes, then the answer is formulated as: $Ans=\sum_{i=1}^{|B|-1}\sum_{j=i+1}^{|B|}\operatorname{dist}(b_i,b_j)$ where $|B|$ denotes the number of the black nodes in the tree, and $\det(b_i,b_j)$ is the length of the simple path from the $i$-th to $j$-th black node.
Write a program to calculate the sum of distances on the tree between every pair of black nodes $Ans$
in the given tree.
1.2 Input
The first line contains an integer $n$, representing the number of nodes in the tree.
The second line contains $n$ space-separated integers ${c1,c_2,\ldots,c_i,\ldots,c_n}$ where $c_i$ is either 0 or l.
$c_i= 1$ indicates that the $i$-th node is black, and $c_i=0$ indicates that the $i$-th node is white.
The following $n-1\operatorname*{lines},{l_1,l_2,\ldots,l_p,\ldots,l{n-1}}$, denoting the structure of the tree follow, each line
$lp$ contains 2 integers $q_p$ and $w_p$, denoting an edge of length $w_p$ between the $\color{red}{p+1}$-th node and the $q{p^-}th$ node.

思路

可能的算法

因为我们要计算的是每一对黑色节点之间的距离，所以我们可以考虑使用动态规划的思想，即将问题分解为子问题，然后逐步求解。

我们先想一下，如果我们要计算一对黑色节点之间的距离，我们可以怎么做呢？

学过树的话，大家肯定都知道LCA-最近公共祖先，我们可以通过LCA来计算两个节点之间的距离。

比如我要计算节点a和节点b之间的距离，那么我们可以先找到他们的LCA，然后计算a到LCA的距离和b到LCA的距离，然后相加即可。

所以我们有了一个算法：

思路1 循环每一对黑色节点，寻找其LCA，然后计算距离，最后相加。

这个思路的时间复杂度是$O(n^3)$，因为我们要循环每一对黑色节点，然后寻找LCA，这个过程的时间复杂度是$O(n)$（这里还不可以用大跳优化到$O(logn)$），所以总的时间复杂度是$O(n^3)$。

很明显，这个算法太慢了，我们需要优化。

优化的思路1 我们可以考虑使用动态规划的思想。

因为如果我们要找到一个黑色节点到LCA的距离，只能一步一步地向上去找，直到抵达LCA。

深入思考一下，我们可以运用树差分的思想：
计算两个节点之间的距离 = 两个节点到根节点的距离和 - LCA到根节点的距离的两倍

这个思路的优越性在于，任意一个节点到根节点的距离只需要计算一次！如果后续我们需要这些数据，我们直接取用即可！

更进一步，我们还可以再用一个动态规划：
计算某个节点到根节点的距离，我们只需要用这个节点的父节点到根节点的距离加上这个节点到父节点的距离即可！

大跳优化 我们可以考虑使用大跳优化：
即我们在计算之前，我们先遍历一次树。假设某个节点的深度为$d$，我们储存这个节点的第$2^i$个祖先，这个祖先的深度为$d-2^i$，这样我们就可以在$O(logn)$的时间内找到任意一个节点的第2^i个祖先。

复杂度分析

计算每个节点到根节点的距离：这一步可以通过一次深度优先搜索（DFS）完成。在这个DFS过程中，每个节点被访问一次，并且在访问其子节点时，我们更新子节点到根节点的距离。这一步的时间复杂度是$O(N)$，其中 N 是树中节点的数量。
寻找最低公共祖先（LCA）：这通常通过预处理父节点数组来实现，使得每次查询的复杂度可以降至$O(1)$（例如使用二进制提升方法）。预处理的复杂度是$ O(NlogN)$。
计算两个节点之间的距离：使用树差分的思想，可以在$O(1)$时间内完成，因为我们已经预处理了到根节点的距离。所以，我们可以先计算每个节点到根节点的距离，然后再寻找LCA，最后累加黑色节点间的距离即可，这样的时间复杂度是$O(n^2)$。
累加黑色节点间的距离：如果黑色节点的数量是$K$，那么在最坏的情况下，需要进行$O(K^2)$次LCA查询和距离计算，因为你可能需要考虑所有黑色节点对之间的距离。所以，这一步的时间复杂度是$O(K^2)$。
预处理：$O(Nlong(N))$（计算到根节点的距离和预处理LCA查询）
查询和计算距离：$O(K^2)$（对于所有黑色节点对）
总的时间复杂度：$O(Nlog(N)+K^2)$

但是这个算法还是太慢了，我们还需要优化！

思路2 我们可以考虑使用树型动态规划的思想。

我们希望只遍历一次树，就可以算出所有的距离。而不是像思路1那样，针对每一对黑色节点，都要遍历一次树。

这里用到了Bell同学的思路，这是一张示意图：

树型动态规划

我们可以看到，这里用到了一个更加复杂的状态转移方程：

$f(u) = f(fa(u)) + siz(A) - siz(B)$

其中：

$f(u)$表示以节点$u$为根的子树中，所有黑色节点到节点$u$的距离之和。
$fa(u)$表示节点$u$的父节点。
$siz(A)$表示集合A中，所有黑色节点的数量。
$siz(B)$表示集合B中，所有黑色节点的数量，也就是节点$u$的子树中，黑色节点的数量。

状态是如何转移的呢？

注意到，

$Ans = \frac{1}{2}\sum_{u\in BlackNodes} f(u),$

就是我们要求的答案。

我们可以看到，$f(u)$是由$f(fa(u))$转移而来的，而$f(fa(u))$是由$f(fa(fa(u)))$转移而来的，而$f(fa(fa(u)))$是由$f(fa(fa(fa(u))))$转移而来的，以此类推。

那么，我们可以得到一个结论：
如果我们知道了$f(fa(u))$，那么我们就可以计算出$f(u)$。（假设siz已知）

这提示我们可以从根节点开始，逐步向下计算。

对于根节点

$f(root) = \sum_{u\in BlackNodes}distToRoot(u)$

因此，我们现在已经清楚了我们要什么：

$distToRoot(u)$：节点$u$到根节点的距离
$siz(A)$：集合$A$（节点$u$的子树）中，所有黑色节点的数量

复杂度分析

计算到根节点的距离$distToRoot()$：使用记忆化搜索，这部分的复杂度为$O(n)$。
计算子树大小和黑色节点的距离$siz()$：这通过一次 DFS 实现，复杂度为$O(n)$。
计算状态转移方程$f()$：节点数量决定，复杂度为$O(n)$。
计算所有黑色节点的距离和：这部分的复杂度是$O(b^2)$，因为它基于每个黑色节点到根的距离和子树中黑色节点的数量。

综上所述，这个算法的时间复杂度是：

$O(n + b^2)$

当$b$接近$n$时，这个算法的时间复杂度是$O(n^2)$。

这是非常好的！（代码见文末） NodeDistance.java

Tarjan算法我们可以考虑使用Tarjan算法。（还没尝试）

对于多次的查询，我们可能会想到并查集，Tarjan算法，在遍历树的同时，我们就可以找到LCA，还有一次性处理多个查询请求的好处（离线算法）。

但是，在这一个题目中，如果我们在遍历树的同时，计算黑色节点之间的距离和，还是相当繁琐的。这里给出一个思路。

步骤1：构建树结构和初始化

构建树：使用输入的边信息构建一棵树，可以使用邻接表表示。
存储节点信息：对于每个节点，存储其颜色 (黑或自) 以及从根节点到该节点的路径长度。

步骤2：深度优先搜索(DFS)和 Tarjan 算法

DFS 遍历：从根节点开始，对树进行深度优先搜索。在这个过程中，记录每个节点的父节点和深度。
黑色节点哈稀表：初始化一个哈希表来存储遍历过程中的黑色节点到当前节点 (LCA) 的距离。

步骤3：结合LCA 查找和距离计算

在DFS中查找LCA：在DFS过程中，当遍历到一个黑色节点时，利用Tarian算法找到它和之前遍历的黑色节点的 LCA。
更新哈希表：将这个黑色节点到 LCA 的距离加入到 LCA 的哈希表中。
计算距离：对于哈希表中的每一个黑色节点，计算它与新遍历的黑色节点之间的距离，并累加。

步骤4：合并并查集

合并集合：在 DFS 后退时 (即完成一个节点的子树遍历后), 合并当前节点与其子节点的并查集。
合并哈希表：同时合并哈希表，将子树中的黑色节点到当前节点的距离更新。

这个算法的时间复杂度是$O(n\alpha(n) + B^2)$，其中$\alpha(n)$是阿克曼函数的反函数，B是黑色节点的数量。

在这里，$\alpha()$反阿克曼函数非常小，对于所有实际的输入大小，它几乎可以认为是一个很小的常数，通常不会超过 4。所以，尽管$\alpha(n)$ 在理论上慢于$log(n)$，但在实际的应用中，它的增长如此之慢，以至于可以认为它比$log(n)$小很多。

但是，由于黑色节点之间的距离仍是通过很多次累加计算得到的，仍然避免不了$O(B^2)$的复杂度。

因此，这个算法的时间复杂度是$O(n + B^2)$，这是一个还不错的结果，但整体思路不如思路2直接了当。有兴趣的读者可以尝试一下哦！

2 Price Sequence

2.1Description

Mario bought $n$ math books and he recorded their prices. The prices are all integers, and the price
sequence is $a={a0,a_2,…a_i,…,a{n-1}}$ of length $n\left(n\leq100000\right)$ .Please help him to manage this price sequence. There are three types of operations:

BUY x: buy a new book with price $x$, thus $x$ is added at the end of $a.$
CLOSEST ADJ PRICE: output the minimum absolute difference between adjacent prices.
CLOSEST-PRICE: output the absolute difference between the two closest prices in the entire sequence.

A total of $m$ operations are performed $(1\leq m\leq100000)$. Each operation is one of the three mentioned types. You need to write a program to perform given operations. For operations “CLOSEST_ADJ PRICE” and “CLOSEST PRICE” you need to output the corresponding answers.

2.2 Input

The first line contains two integers $n$ and $m$, representing the length of the original sequence and the
number of operations.
The second line consists of $n$ integers, representing the initial sequence $a.$
Following that are $m$ lines, each containing one operation: either BUY x, CLOSEST_ADJ PRICE, or
CLOSEST PRICE (without extra spaces or empty lines).

思路

CLOSEST ADJ PRICE

这个操作很简单，我们只需要维护一个最小的相邻差值即可。随着我们不断地添加新的价格，我们只需要比较新的价格和上一个价格的差值，然后更新最小的相邻差值即可。

CLOSEST PRICE

这个操作稍微复杂一点，我们需要维护一个最小的价格差值。深入思考一下就会发现，只要将价格排序，然后比较相邻的两个价格差值，就可以得到最小的价格差值。

但是，我们不可能每次都对价格进行排序，这样的时间复杂度是$O(nlogn)$。

既然又需要插入，又需要排序。我们很容易就能想到红黑树：一种自平衡的二叉查找树，它的时间复杂度是$O(logn)$。

插入之后，我们只需要计算插入位置的前后之间的差值，再与原来相邻价格的差值的最小值相比较，这样即可得到CLOSEST PRICE。

更进一步的优化

由于作业要求中，有两个样例不需要我们维护CLOEST PRICE，而其中BUY的数据量可能又相当大。所以我们需要优化CLOSEST PRICE的维护。

Test Case No.	Constraints
1-4	n ≤ $10^3$, m ≤ $10^3$
5-6	There is no CLOSEST PRICE operation
7-9	$a_i$ and $x$ are uniformly distributed at random within the range [0, $10^{12}$]
10	No additional constraints

我们可以考虑CLOEST PRICE用到时再计算。将BUY的操作储存起来，CLOSEST ADJ PRICE依然随着BUY而更新，但请求CLOEST PRICE时，再将所有BUY记录一次性插入红黑树中，然后进行计算。这样，我们CLOEST PRICE的计算就不会影响CLOSEST ADJ PRICE的效率了！

（代码见文末） PriceSequence.java

NodeDistance.java

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

// Class name changed to match file name NodeDistance.java
public class NodeDistance {

    // Define class-level variables
    static int[] parent, length, blackAndWhite;
    static long[] f, distDP, blackNum;
    static Map<Integer, List<Integer>> children = new HashMap<>();
    static int lineNum;

    public static void main(String[] args) throws NumberFormatException, IOException {
        // Initialize arrays with an offset for 1-indexed access
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        lineNum = Integer.parseInt(input.readLine());
        blackAndWhite = new int[lineNum + 1];
        parent = new int[lineNum + 1];
        length = new int[lineNum + 1];
        f = new long[lineNum + 1];
        distDP = new long[lineNum + 1];
        blackNum = new long[lineNum + 1];

        // Read the color information for nodes
        StringTokenizer st = new StringTokenizer(input.readLine());
        for (int i = 1; i <= lineNum; i++) {
            blackAndWhite[i] = Integer.parseInt(st.nextToken());
        }

        // Read and construct the tree structure
        for (int i = 1; i < lineNum; i++) {
            st = new StringTokenizer(input.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (a > i + 1) {
                parent[a] = i + 1;
                addChild(i + 1, a);
                length[a] = b;
            } else {
                parent[i + 1] = a;
                addChild(a, i + 1);
                length[i + 1] = b;
            }
        }

        input.close();

        // Determine the structure of the tree
        boolean isCircle = true, isLine = true;
        for (int i = 2; i <= lineNum; i++) {
            if (parent[i] != 1) {
                isCircle = false;
                break;
            }
        }

        // Check if the tree structure is a line
        for (int i = 2; i <= lineNum; i++) {
            List<Integer> childList = children.get(parent[i]);
            if (childList != null)
                if (childList.size() > 1 || (parent[i] != i - 1)) {
                    isLine = false;
                    break;
                }
        }

        // Collect black nodes for further processing
        List<Integer> blackNodesList = new ArrayList<>();
        for (int i = 1; i <= lineNum; i++) {
            if (blackAndWhite[i] == 1)
                blackNodesList.add(i);
        }
        int[] blackNodes = blackNodesList.stream().mapToInt(Integer::intValue).toArray();

        // Optimize calculation based on the tree structure
        if (isLine) {
            calculateLineDistance(blackNodes);
            return;
        } else if (isCircle) {
            calculateCircleDistance(blackNodes);
            return;
        }

        // Pre-compute the distance from each node to the root
        Arrays.fill(f, -1);
        Arrays.fill(blackNum, -1);
        Arrays.fill(distDP, -1);
        long totalDistanceToRoot = 0;
        for (int blackNode : blackNodes) {
            totalDistanceToRoot += distToRoot(blackNode);
        }
        f[1] = totalDistanceToRoot;

        // Compute the size of the subtree and distances for black nodes
        sizeDfs(1);  //gx
        long sumDistance = 0;
        for (int blackNode : blackNodes) {
            sumDistance += dfs(blackNode);
        }

        // Output the total distance
        System.out.println(sumDistance / 2);
    }

    // Method to calculate distances in a linear tree
    private static void calculateLineDistance(int[] blackNodes) {
        int[] distanceToRoot = new int[lineNum + 1];
        for (int i = 1; i <= lineNum; i++) {
            if (parent[i] != 0) { // If parent exists
                distanceToRoot[i] = distanceToRoot[parent[i]] + length[i];
            }
        }

        long totalDistance = 0;
        for (int i = 0; i < blackNodes.length - 1; i++) {
            for (int j = i + 1; j < blackNodes.length; j++) {
                totalDistance += Math.abs(distanceToRoot[blackNodes[i]] - distanceToRoot[blackNodes[j]]);
            }
        }
        System.out.println(totalDistance);
    }

    // Method to calculate distances in a circular tree
    private static void calculateCircleDistance(int[] blackNodes) {
        long totalDistance = 0;
        for (int i = 0; i < blackNodes.length; i++) {
            for (int j = i + 1; j < blackNodes.length; j++) {
                totalDistance += length[blackNodes[i]] + length[blackNodes[j]];
            }
        }
        System.out.println(totalDistance);
    }

    // Helper method to compute distance to root for a given node
    public static long distToRoot(int node) {
        if (node == 1) return 0;
        if (distDP[node] == -1) {
            distDP[node] = (long) length[node] + distToRoot(parent[node]);
        }
        return distDP[node];
    }

    // Helper method to add a child to a node in the tree
    public static void addChild(int par, int child) {
        children.computeIfAbsent(par, k -> new ArrayList<>()).add(child);
    }

    // DFS method to calculate distances from a node to all black nodes
    public static long dfs(int node) {
        if (node == 1) return f[1];
        if (f[node] == -1) {
            f[node] = dfs(parent[node]) + length[node] * (blackNum[1] - 2 * blackNum[node]);
        }
        return f[node];
    }

    // DFS method to calculate the size of subtrees
    public static void sizeDfs(int node) {
        if (blackNum[node] != -1) return;
        blackNum[node] = blackAndWhite[node] == 1 ? 1 : 0;
        List<Integer> childList = children.get(node);
        if (childList != null) {
            for (int child : childList) {
                sizeDfs(child);
                blackNum[node] += blackNum[child];
            }
        }
    }
}

PriceSequence.java

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

public class PriceManager {
    private TreeSet<Long> prices; // TreeSet to maintain sorted unique prices
    private long minAdjacentDiff, lastPrice = -1; // Track the minimum adjacent difference and the last price added
    private int pIndex = 0; // Pointer to process pending BUY operations
    private List<Long> pendingBuys; // Store pending BUY operations
    private Long minPriceDiff = Long.MAX_VALUE; // Track the minimum difference between any two prices

    public PriceManager() {
        prices = new TreeSet<>();
        pendingBuys = new ArrayList<>();
        minAdjacentDiff = Long.MAX_VALUE;
    }

    // Adds all new prices and updates the minimum price difference incrementally
    public void addAllPrice(List<Long> priceList) {
        for (Long price : priceList) {
            // Skip processing if the minimum difference is already 0
            if(minPriceDiff == 0) break;

            // Find the higher and lower prices for comparison
            Long higher = prices.higher(price);
            Long lower = prices.lower(price);

            // If the price already exists, the minimum difference is 0
            if(prices.contains(price)) {
                minPriceDiff = 0L;
            } else {
                // Update the minimum difference based on the higher and lower neighbors
                if (higher != null) {
                    minPriceDiff = Math.min(minPriceDiff, Math.abs(higher - price));
                }
                if (lower != null) {
                    minPriceDiff = Math.min(minPriceDiff, Math.abs(price - lower));
                }
            }
            prices.add(price);
        }
    }

    // Records a pending BUY operation to be processed later
    public void recordBuy(long price) {
        pendingBuys.add(price);
    }

    // Process all pending BUY operations and update the minimum adjacent difference
    private void processPendingBuys() {
        while (pIndex < pendingBuys.size()) {
            long price = pendingBuys.get(pIndex++);
            if (lastPrice != -1) {
                minAdjacentDiff = Math.min(minAdjacentDiff, Math.abs(lastPrice - price));
            }
            lastPrice = price;
        }
    }

    // Returns the closest adjacent price
    public long closestAdjacentPrice() {
        processPendingBuys();
        return minAdjacentDiff;
    }

    // Returns the closest price difference between any two prices
    public long closestPrice() {
        this.addAllPrice(pendingBuys);
        pendingBuys.clear(); // Clear the pending BUY operations after processing
        pIndex = 0;
        return minPriceDiff;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(input.readLine());

        int n = Integer.parseInt(st.nextToken()); // Initial number of prices
        int m = Integer.parseInt(st.nextToken()); // Number of operations

        PriceManager manager = new PriceManager();

        // Record initial BUY operations
        st = new StringTokenizer(input.readLine());
        for (int i = 0; i < n; i++) {
            manager.recordBuy(Long.parseLong(st.nextToken()));
        }

        // Process operations
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(input.readLine());
            String operation = st.nextToken();
            switch (operation) {
                case "BUY":
                    long price = Long.parseLong(st.nextToken());
                    manager.recordBuy(price);
                    break;
                case "CLOSEST_ADJ_PRICE":
                    System.out.println(manager.closestAdjacentPrice());
                    break;
                case "CLOSEST_PRICE":
                    System.out.println(manager.closestPrice());
                    break;
            }
        }

        input.close(); // Close the input stream
    }
}

Download Links 作业原文档下载

CSC3100 Assignment3

1 Node Distance

1.1 Description

1.2 Input

思路