C. 最大树值 题解

---

一、题意理解

给定一棵 $n$ 个顶点的树，每条边 $(u, v)$ 有两个权值 $x$ 和 $y$。给每个顶点赋一个 $1$ 到 $n$ 的排列值 $p_i$。

对于边 $(u, v)$（$u < v$），其贡献为：

$$\begin{cases} x, & \text{若 } p_u > p_v, \\[4pt] y, & \text{否则}. \end{cases} $$

目标是最大化所有边的贡献之和。

---

二、核心观察

命题：对于每条边 $(u, v, x, y)$，我们可以使其贡献等于 $\max(x, y)$。

证明：

为每条边赋予一个方向：

• 若 $x \leq y$，则期望 $p_u < p_v$（使贡献为 $y$），定向为 $u \to v$。
• 若 $x > y$，则期望 $p_u > p_v$（使贡献为 $x$），定向为 $v \to u$。

这样，每条边都被赋予了一个方向。

---

三、DAG 的构造

断言：按上述规则定向后的图是一个有向无环图（DAG）。

证明：

由于原图是一棵树（无环），给每条边定向后不会产生新的环。假设存在一个有向环 $v_1 \to v_2 \to \dots \to v_k \to v_1$，则根据定向规则，必须有：

$$p_{v_1} < p_{v_2} < \dots < p_{v_k} < p_{v_1}$$

这产生了矛盾 $p_{v_1} < p_{v_1}$。因此定向后的图无环。

---

四、拓扑排序构造排列

既然定向后的图是 DAG，我们可以对其进行拓扑排序。

设拓扑排序得到的顺序为 $order_1, order_2, \dots, order_n$。

令排列 $p$ 满足：

$$p_{order_i} = i$$

即：拓扑序中越靠前的顶点，赋值越小。

正确性验证：

对于定向边 $u \to v$，$u$ 在拓扑序中出现在 $v$ 之前，因此 $p_u < p_v$，这正是定向时所期望的大小关系。

因此，每条边的贡献都取到了 $\max(x, y)$，总和达到理论最大值。

---

五、算法流程

1. 读入树的所有边 $(u, v, x, y)$。
2. 对于每条边：
   • 若 $x > y$，定向为 $v \to u$（期望 $p_v < p_u$）。
   • 若 $x \leq y$，定向为 $u \to v$（期望 $p_u < p_v$）。
3. 构建有向图，计算每个顶点的入度。
4. 将所有入度为 $0$ 的顶点加入队列。
5. 进行拓扑排序：依次取出队首顶点 $u$，为其赋值 $p_u = \text{当前序号}$，然后将 $u$ 的所有出边指向的顶点入度减 $1$，若入度变为 $0$ 则入队。
6. 输出排列 $p$。

---

六、标程解析

void solve() {
  int n;
  std::cin >> n;
 
  std::vector<int> deg(n, 0);
  std::vector<std::vector<int>> g(n);
  std::vector<std::vector<int>> gg(n);
 
  std::vector<Edge> e(n - 1);
 
  for (auto &[u, v, x, y] : e) {
    std::cin >> u >> v >> x >> y;
    u--, v--;
    if (x > y) {
      g[u].push_back(v);       // u -> v 期望 p_u > p_v
      gg[v].push_back(u);      // 反向边，用于拓扑排序
      deg[u]++;                // u 是"大端"，入度增加
    } else {
      g[v].push_back(u);       // v -> u 期望 p_v > p_u
      gg[u].push_back(v);
      deg[v]++;
    }
  }
 
  std::queue<int> q;
  for (int i = 0; i < n; i++) {
    if (deg[i] == 0) {
      q.push(i);
    }
  }
 
  std::vector<int> p(n);
 
  for (int i = 1; i <= n; i++) {
    int u = q.front();
    p[u] = i;                  // 拓扑序中第 i 个被赋值的顶点
    q.pop();
 
    for (const auto &v : gg[u]) {
      deg[v]--;
      if (deg[v] == 0) {
        q.push(v);
      }
    }
  }
  
  for (int x : p) {
    std::cout << x << ' ';
  }
}

步骤详解：

1. 读入 $n$ 和 $n-1$ 条边。
2. 根据 $x$ 和 $y$ 的大小关系定向：
   • 若 $x > y$：期望 $p_u > p_v$，即 $u$ 应该比 $v$ 大。在拓扑排序中，$u$ 应后出现。因此添加边 $u \to v$，并增加 $u$ 的入度（因为 $u$ 是依赖方，需要等 $v$ 先赋值）。
   • 若 $x \leq y$：期望 $p_u < p_v$，类似地添加边 $v \to u$。
3. 将所有入度为 $0$ 的顶点入队（它们可以最先被赋值）。
4. 进行 BFS 拓扑排序，按出队顺序依次赋值 $1, 2, \dots, n$。
5. 输出排列。

注意：标程中的 deg 和边方向的定义与常见拓扑排序略有不同：

• g[u] 存储从 $u$ 出发的边（$u$ 应更大）。
• gg[u] 存储指向 $u$ 的边（$u$ 依赖的顶点）。
• deg[u] 表示有多少顶点依赖 $u$（即 $u$ 必须先被赋值）。

---

七、代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, x, y;
};

void solve() {
    int n;
    cin >> n;
    
    vector<int> deg(n, 0);
    vector<vector<int>> g(n);   // g[u]: u 应该更大（后赋值）
    vector<vector<int>> rg(n);  // rg[u]: 依赖于 u 的顶点
    
    for (int i = 0; i < n - 1; i++) {
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        u--, v--;
        
        if (x > y) {
            // 期望 p_u > p_v，即 u 应比 v 大 -> u 后赋值
            g[u].push_back(v);
            rg[v].push_back(u);
            deg[u]++;
        } else {
            // 期望 p_v > p_u 或 p_u < p_v，即 v 应比 u 大 -> v 后赋值
            g[v].push_back(u);
            rg[u].push_back(v);
            deg[v]++;
        }
    }
    
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 0) q.push(i);
    }
    
    vector<int> p(n);
    int cur = 1;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        p[u] = cur++;
        
        for (int v : rg[u]) {
            deg[v]--;
            if (deg[v] == 0) q.push(v);
        }
    }
    
    for (int i = 0; i < n; i++) {
        cout << p[i] << " \n"[i == n - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) solve();
    
    return 0;
}

---

八、样例验证

样例 1

3
1 2 2 1
2 3 3 2

• 边 $(1,2)$：$x=2 > y=1$，期望 $p_1 > p_2$。定向 $1 \to 2$（$1$ 应更大，后赋值），$\deg[1]++$。
• 边 $(2,3)$：$x=3 > y=2$，期望 $p_2 > p_3$。定向 $2 \to 3$，$\deg[2]++$。

入度：$\deg = [1, 1, 0]$。

拓扑排序：初始 $q = [3]$（入度为 $0$）。

• 取出 $3$：$p_3 = 1$。
• $\deg[2]-- \to \deg[2]=0$，入队 $2$。
• 取出 $2$：$p_2 = 2$。
• $\deg[1]-- \to \deg[1]=0$，入队 $1$。
• 取出 $1$：$p_1 = 3$。

排列 $p = [3, 2, 1]$，最大值 $= \max(2,1) + \max(3,2) = 2 + 3 = 5$ ✅

---

九、复杂度分析

• 构建有向图：$O(n)$。
• 拓扑排序：$O(n)$。
• 每个测试用例总复杂度 $O(n)$。
• $\sum n \leq 2 \times 10^5$，完全可行。
• 空间复杂度 $O(n)$。