题意回顾

我们需要构造长度为 $n$ 的序列 $x_1, \dots, x_n$，满足：

1. 变量范围约束：$l_i \le x_i \le r_i$，其中 $1 \le l_i \le r_i \le k$，$k \in \{3,4,5\}$
2. 差值约束：$m$ 个形如 $|x_{p_j} - x_{q_j}| \le b_j$ 的条件

目标函数： [ W = 10^6 \cdot G + \sum_{i=2}^{k-1} c_i v_i ] 其中：

• $c_i$ = 值为 $i$ 的变量个数
• $G$ = 满足 $|x_i - x_j| \le 1$ 的有序对 $(i,j)$ 数量

有 $q$ 组询问，每组给出 $v_2, \dots, v_{k-1}$，求最大 $W$。

数据范围：$k \le 5$，$\sum q \le 3 \times 10^5$。

---

关键分析与转化

1. 目标函数简化

$G$ 是满足 $|x_i - x_j| \le 1$ 的有序对数量。注意：

• 当 $x_i = x_j$ 时，对任意 $i,j$ 都贡献 1（包括 $i=j$）
• 当 $|x_i - x_j| = 1$ 时，贡献 1

设 $E$ 为满足 $|x_i - x_j| = 1$ 的无序对 $\{i,j\}$ 的数量，则： [ G = n^2 + 2E ] 因为：

• $n^2$ 来自所有 $|x_i - x_j| = 0$ 的有序对（包括 $i=j$）
• 每个 $|x_i - x_j| = 1$ 的无序对贡献 2 个有序对

因此： [ W = 10^6 \cdot (n^2 + 2E) + \sum_{i=2}^{k-1} c_i v_i ] $n^2$ 是常数，在最大化时可不考虑。

---

2. 约束图模型

将变量看作节点，差值约束 $|x_p - x_q| \le b$ 看作边。

关键性质：如果两个变量之间有边 $|x_p - x_q| \le b$，则它们的取值必须在某个长度为 $b+1$ 的区间内。

更一般地，对于连通分量，所有变量的取值必须在某个长度为 $d+1$ 的区间内，其中 $d$ 是连通分量中所有边 $b_j$ 的最大值。

---

3. 连通分量处理

用并查集求出所有连通分量。对每个连通分量 $C$：

• 计算 $d_C = \max\{b_j \mid \text{边 } (p_j,q_j) \text{ 在 } C \text{ 内}\}$
• 计算该分量中所有变量的整体取值范围： [ L_C = \max{\text{所有变量的 } l_i}, \quad R_C = \min{\text{所有变量的 } r_i} ] 且必须满足 $R_C - L_C \le d_C$

实际上，我们需要找到所有变量都能取的公共区间 $[L, R]$，满足：

• $L \ge l_i$，$R \le r_i$ 对所有 $i \in C$
• $R - L \le d_C$

---

算法步骤

阶段 1：预处理连通分量

// 并查集
struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n + 1) {
        for (int i = 1; i <= n; i++) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        parent[find(y)] = find(x);
    }
};

// 处理每个连通分量
void process_component(int comp_id, vector<int>& nodes) {
    int L = 1, R = k;  // 初始范围
    
    // 计算整体取值范围
    for (int i : nodes) {
        L = max(L, l[i]);
        R = min(R, r[i]);
    }
    
    // 考虑差值约束进一步限制范围
    int max_b = 0;
    for (auto edge : edges) {
        if (comp[edge.p] == comp_id && comp[edge.q] == comp_id) {
            max_b = max(max_b, edge.b);
        }
    }
    
    // 可能的取值区间
    vector<pair<int, int>> valid_intervals;
    for (int start = L; start <= R; start++) {
        int end = min(R, start + max_b);
        if (end >= start) {
            valid_intervals.push_back({start, end});
        }
    }
    
    component_data[comp_id] = {nodes.size(), valid_intervals};
}

阶段 2：枚举分量取值方案

由于 $k \le 5$，每个连通分量的可能取值区间很少，我们可以枚举所有分量的取值组合。

但直接枚举所有分量不可行（分量数可能很多）。观察发现：

$E$ 只与相邻值的变量对有关，而相邻值只可能出现在：

• 同一连通分量内不同变量取相邻值
• 不同连通分量但变量取值相邻

但第二种情况很难处理。实际上，标准解法利用了 $k$ 很小的特点：

将所有变量按最终取值分类，设 $cnt[i]$ 表示取值为 $i$ 的变量数，则： [ E = \sum_{i=1}^{k-1} cnt[i] \cdot cnt[i+1] ] 因为每个 $i$ 与 $i+1$ 之间的无序对都贡献 1。

所以： [ W = 10^6 \cdot \left(n^2 + 2\sum_{i=1}^{k-1} cnt[i] \cdot cnt[i+1]\right) + \sum_{i=2}^{k-1} cnt[i] \cdot v_i ]

问题转化为：在约束下最大化该函数。

---

阶段 3：动态规划求解

设 $dp[i][s]$ 表示考虑前 $i$ 个连通分量，当前已分配变量的取值状态为 $s$ 时的最大权值（去掉常数 $10^6 n^2$）。

但状态 $s$ 需要记录 $cnt[1..k]$，这在 $k=5$ 时状态数太大。

优化：由于 $k$ 很小，我们可以枚举全局的 $cnt[1..k]$ 分布，然后检查是否存在分配方案满足所有约束。

具体步骤：

1. 枚举所有可能的 $cnt[1..k]$（满足 $\sum cnt[i] = n$）
2. 对每种分布，检查是否满足：
   • 每个连通分量的变量都能在某个区间内取值
   • 分布与各分量的可能区间兼容
3. 对可行的分布计算 $W$，取最大值

---

高效算法框架

对于 $k \le 5$，我们可以用整数划分的思想：

// 枚举所有可能的取值分布
vector<vector<int>> distributions;
for (int c1 = 0; c1 <= n; c1++) {
    for (int c2 = 0; c2 <= n - c1; c2++) {
        for (int c3 = 0; c3 <= n - c1 - c2; c3++) {
            for (int c4 = 0; c4 <= n - c1 - c2 - c3; c4++) {
                int c5 = n - c1 - c2 - c3 - c4;
                if (c5 < 0) continue;
                distributions.push_back({c1, c2, c3, c4, c5});
            }
        }
    }
}

// 对每个分布检查可行性并计算W
vector<bool> feasible(distributions.size(), false);
for (int idx = 0; idx < distributions.size(); idx++) {
    auto& cnt = distributions[idx];
    if (check_feasible(cnt, components)) {
        feasible[idx] = true;
    }
}

// 回答询问
for (auto& query : queries) {
    ll best = -1e18;
    for (int idx = 0; idx < distributions.size(); idx++) {
        if (!feasible[idx]) continue;
        auto& cnt = distributions[idx];
        ll val = 0;
        for (int i = 1; i <= k-1; i++) {
            val += 2e6 * cnt[i-1] * cnt[i];  // 2E * 10^6
        }
        for (int i = 2; i <= k-1; i++) {
            val += cnt[i-1] * query.v[i-2];  // c_i * v_i
        }
        best = max(best, val);
    }
    cout << best + 1e6 * n * n << "\n";  // 加上常数项
}

check_feasible 函数需要检查：是否存在方案将各连通分量的变量分配到取值，使得全局分布为 $cnt$，且每个连通分量的变量都在其可行区间内。

这可以用网络流或贪心匹配解决。

---

网络流检查可行性

建图：

• 源点 → 取值类：容量 $cnt[i]$
• 取值类 → 连通分量：如果该分量能取该值，容量为分量大小
• 连通分量 → 汇点：容量为分量大小

存在可行方案当且仅当最大流等于 $n$。

---

复杂度优化

由于 $k$ 很小且 $n$ 可能大，直接枚举所有分布不可行。实际做法是：

1. 预处理所有连通分量的可能取值区间
2. 对每个询问，用线性规划或贪心直接求最优分布
3. 利用 $k$ 小的特点，将问题转化为低维空间中的凸包问题

---

总结

本题的关键在于：

1. 目标函数转化：将 $G$ 表示为 $n^2 + 2E$，$E$ 用 $cnt[i] \cdot cnt[i+1]$ 表示
2. 约束图分析：利用连通分量和差值约束确定变量取值范围
3. 枚举优化：利用 $k$ 小的特点，枚举分布或直接求解低维线性规划
4. 可行性检查：用网络流或贪心验证分布可行性

算法标签：图论、线性规划、组合数学