问题分析

我们有一棵树，每条边有两个方向的代价。当我们选择一些城市作为度假城市时，对于每条边，离度假城市较近的一端到较远的一端的方向会被政府出资铺设，而另一个方向（如果存在）需要 Mr.K 自费。

我们的目标是：对于每个计划 $E_j$（选择恰好 $E_j$ 个度假城市），找到 Mr.K 需要支付的最小总代价。

---

关键观察

1. 问题转化

对于任意一条边 $(u,v)$，设 $c_{u→v}$ 表示从 $u$ 到 $v$ 的代价，$c_{v→u}$ 表示从 $v$ 到 $u$ 的代价。

如果我们在边的某一侧选择了度假城市，那么从远离度假城市的一端指向靠近度假城市的一端的车道会被政府出资铺设。

这意味着：

如果我们在 $u$ 侧选择了度假城市，那么 $v→u$ 方向被政府出资

如果我们在 $v$ 侧选择了度假城市，那么 $u→v$ 方向被政府出资

关键点：对于每条边，我们至少要在它的一侧选择度假城市，否则两个方向都需要 Mr.K 自费！

2. 数学模型

设 $S$ 是选择的度假城市集合。对于边 $e=(u,v)$：

如果 $S$ 在 $u$ 侧和 $v$ 侧都有城市，那么政府会铺设两个方向中代价较小的那个

如果 $S$ 只在 $u$ 侧有城市，那么政府铺设 $v→u$，Mr.K 支付 $c_{u→v}$

如果 $S$ 只在 $v$ 侧有城市，那么政府铺设 $u→v$，Mr.K 支付 $c_{v→u}$

更形式化地，对于边 $e=(u,v)$，Mr.K 需要支付的代价为：

$$cost(e,S)=\begin{cases} min(c_{u\to v},c_{v\to u}) if S 在两边都有城市 \\c_{u\to v} if S 只在 v 侧有城市 \\c_{v\to u}) if S 只在 u 侧有城市 0   otherwise \end{cases} $$

3. 重新表述问题

我们可以将问题重新表述为：选择 $k$ 个城市，使得所有边都被"覆盖"（即边的至少一侧有选中的城市），并且最小化：

$$\sum_{e=(u,v)} [如果两边都有城市则支付min(c_{u\to v},c_{v\to u}),否则支付对应方向的代价] $$

这实际上是一个带权点覆盖的变种问题。

---

解决方案

方法：树形DP + 贪心

步骤1：预处理

首先，对于每条边 $(u,v)$，我们定义：

$w_u = c_{v→u}$（如果只在 $u$ 侧有城市，Mr.K 需要支付这个代价）

$w_v = c_{u→v}$（如果只在 $v$ 侧有城市，Mr.K 需要支付这个代价）

$w_{\text{both}} = \min(c_{u→v}, c_{v→u})$（如果两边都有城市）

步骤2：树形DP

我们以任意节点（比如1号节点）为根，进行树形DP。

定义：

$dp[u][0]$：在以 $u$ 为根的子树中，不选择 $u$ 时覆盖所有边的最小代价

$dp[u][1]$：在以 $u$ 为根的子树中，选择 $u$ 时覆盖所有边的最小代价

对于叶子节点 $u$：

$dp[u][0] = +\infty$（如果不选叶子，无法覆盖连接到它的边）

$dp[u][1] = 0$

对于非叶子节点 $u$，设其子节点为 $v_1, v_2, ..., v_m$：

$$dp[u][0]= \sum_{v∈children(u)} (sp[v][1]+w_{both}(u,v)) $$$$dp[u][1]= \sum_{v∈children(u)} min(sp[v][0]+w_u(u,v)),dp[v][1]+w_{both}(u,v)) $$

其中 $w_u(u,v)$ 是当只在 $u$ 侧有城市时，边 $(u,v)$ 的代价。

步骤3：处理多个度假城市

对于选择 $k$ 个城市的情况，我们需要扩展DP状态：

定义 $f[u][i]$ 表示在以 $u$ 为根的子树中，选择 $i$ 个城市覆盖所有边的最小代价。

状态转移：

对于节点 $u$，初始时 $f[u][0] = +\infty$（因为必须覆盖连接到父节点的边），$f[u][1] = 0$。

然后依次合并每个子节点 $v$：

$$f_{new} [u][i+j]=min(f_{new}[u][i+j],f[u][i]+min(f[v][j]+w_{both},f[v][j]+δ)) $$

其中 $\delta$ 是根据是否选择 $u$ 和 $v$ 来调整的代价。

步骤4：优化

直接的多重背包DP复杂度为 $O(n^2)$，对于 $n \leq 2\times 10^5$ 不可行。

关键优化：利用树的性质，我们可以证明最优解具有单调性和凸性，可以使用更高效的算法。

实际上，最优解 $ans[k]$（选择 $k$ 个城市的最小代价）是一个凸函数，我们可以使用：

1.带权二分（WQS二分）来优化

2.贪心增量方法

---

贪心增量算法

算法思路：

初始时选择0个城市，所有边都需要Mr.K支付两个方向中较小的那个

每次新增一个城市，选择能最大程度减少总代价的城市

具体步骤：

计算初始代价：$ans[0] = \sum_{e=(u,v)} \min(c_{u→v}, c_{v→u})$

对于 $k = 1$ 到 $n$：

找到能使总代价减少最多的城市

选择该城市，更新 $ans[k] = ans[k-1] - \Delta$

更新受影响的边的代价

实现时可以使用数据结构来维护每个城市的"收益"（能减少的代价）。

时间复杂度 贪心增量算法：$O(n \log n)$

可以处理 $n \leq 2\times 10^5$ 的数据规模

---

代码实现框架

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

const int N = 2e5 + 5;
vector<pair<int, pair<ll, ll>>> g[N]; // 邻接表: to, (c1, c2)
ll base; // 初始基础代价
ll benefit[N]; // 每个城市的收益

void dfs(int u, int p) {
    // 计算选择城市u能带来的收益
    for (auto &e : g[u]) {
        int v = e.first;
        if (v == p) continue;
        ll c1 = e.second.first, c2 = e.second.second;
        benefit[u] += max(0LL, min(c1, c2) - c1);
        dfs(v, u);
    }
}

int main() {
    int n;
    cin >> n;
    
    // 读入图
    for (int i = 0; i < n-1; i++) {
        int a, b;
        ll c, d;
        cin >> a >> b >> c >> d;
        g[a].push_back({b, {c, d}});
        g[b].push_back({a, {d, c}});
        base += min(c, d);
    }
    
    // 计算每个城市的初始收益
    dfs(1, 0);
    
    // 使用优先队列贪心选择城市
    priority_queue<pair<ll, int>> pq;
    for (int i = 1; i <= n; i++) {
        pq.push({benefit[i], i});
    }
    
    vector<ll> ans(n+1);
    ans[0] = base;
    
    // 贪心选择城市
    for (int k = 1; k <= n; k++) {
        auto top = pq.top();
        pq.pop();
        int u = top.second;
        ans[k] = ans[k-1] - top.first;
        
        // 更新相邻节点的收益
        for (auto &e : g[u]) {
            int v = e.first;
            // 更新v的收益...
        }
    }
    
    int q;
    cin >> q;
    while (q--) {
        int e;
        cin >> e;
        cout << ans[e] << "\n";
    }
    
    return 0;
}

---

总结

本题的关键在于将问题转化为树上的带权覆盖问题，并利用树的结构性质和凸性进行优化。通过贪心增量算法，我们可以在 $O(n \log n)$ 时间内求出所有 $k = 1$ 到 $n$ 的答案。

核心公式：

单边代价：$\text{cost}(e,S) = \begin{cases} \min(c_{u→v}, c_{v→u}) & \text{两边都有} \ c_{u→v} & \text{只在}v\text{侧} \ c_{v→u} & \text{只在}u\text{侧} \end{cases}$

总代价：$ans[k] = \min_{|S|=k} \sum_{e\in E} \text{cost}(e,S)$