【LOJ】【带权二分】【树形DP】#2478 「九省联考 2018」林克卡特树_综合

LOJ #2478.「九省联考 2018」林克卡特树

题目大意

◇题目传送门◆

给定一棵有负权边的树，现在必须恰好删去 $K$ 条边，并加上恰好 $K$ 条权值为 $0$ 的边，要求最大化它的直径长度。

分析

考虑连上 $K$ 条权值为 $0$ 的边的意义：

似乎并没有什么意义。只是将一条直径拆成了 $K + 1$ 条链带权的链而已。

然而我们也可以用这个方法将原问题转化为求解 $K + 1$ 条点不相交的链的最大边权和。

为了描述方便，我们强制定义一个点也属于一条链。（可以看做它形成了一个自环）

设状态 $f (u, 0 / 1 / 2, k)$ 表示以 $u$ 为根的子树中，选出 $k$ 条点不相交的链的最大边权和，且 $u$ 的度数为 $0, 1, 2$ ，且强制每个点对应它到父亲的边。

我们尝试列出几个状态转移方程：（其中 $v$ 是 $u$ 的儿子）

$f(u,0,i)=\max\{f(u,0,j)+f(v,0,i-j)\}$ ：当 $u$ 的度数为 $0$ 时，可知这个点一定不在链上，直接与子树合并答案即可。
$f(u,1,i)=\max\{f(u,0,j)+f(v,1,i-j)+w_{u,v},f(u,1,j)+f(v,0,i-j)\}$ ：当 $u$ 的度数为 $1$ 时，这时 $u$ 是某条链的端点，我们可以将它分成自己本身有一条链、儿子有一条链两种情况，分别取最大即可。
$f(u,2,i)=\max\{f(u,1,j)+f(v,1,i-j-1)+w_{u,v},f(u,2,j)+f(v,1,i-j)\}$ ：这时 $u$ 在某条链的中部。我们可以认为这种情况可以由 $u, v$ 分别是两条点不相交的链的端点或者 $u$ 在某条链中部， $v$ 在另外一条链上所形成的。
$f(u,0,i)=\max\{f(u,0,i),f(u,1,i-1),f(u,2,i)\}$ ：把答案合并起来。

于是答案就是 $f (1, 0, K + 1)$

然而这个算法是 $O(NK^2)$ 的，显然过不了。。。

考虑优化：

我们令 $K$ 为横坐标，求得的最优解为纵坐标，然后打表发现这个东西有凸性。于是果断上带权二分。

我们给每条路径二分一个附件权值 $v$ ，在新增一条链时减掉 $v$ ，这样，在 $v$ 较大时可以选出更多的点不相交的链出来， $v$ 较小时可以选出更少的点不相交的链出来。于是我们二分这个 $v$ ，二分到我们分出的链恰好有 $K + 1$ 条出来，最后计算答案时再加回即可。

而如何计算这个链的数量，我们可以用上面那个树形 DP 。只不过将最后一维去掉，并在 DP 时统计链的数量即可。

由于有负权边，故二分的范围要弄大一点。

参考代码

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long ll;
const int Maxn = 3e5;
const ll INF = 1E12;int N, K;
vector<pair<int, int> > G[Maxn + 5];
void addedge(int u, int v, int w) {
    G[u].push_back(make_pair(v, w));G[v].push_back(make_pair(u, w));
}struct State {
    ll val;int cnt;State(){
    }State(ll a, int b) {
    val = a, cnt = b;}State operator + (const State &rhs) {
    return State(val + rhs.val, cnt + rhs.cnt);}bool operator < (const State &rhs) const {
    return val == rhs.val ? cnt > rhs.cnt : val < rhs.val;}
};
State f[3][Maxn + 5];void DFS(int u, int fa, ll val) {
    for(int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i].first;ll w = G[u][i].second;if(v == fa) continue;DFS(v, u, val);f[2][u] = max(f[2][u] + f[0][v], f[1][u] + f[1][v] + State(w - val, 1));f[1][u] = max(f[1][u] + f[0][v], f[0][u] + f[1][v] + State(w, 0));f[0][u] = f[0][u] + f[0][v];}f[0][u] = max(f[0][u], max(f[1][u] + State(-val, 1), f[2][u]));
}bool check(ll val) {
    for(int i = 1; i <= N; i++) {
    f[0][i] = f[1][i] = State(0, 0);f[2][i] = State(-val, 1);}DFS(1, 0, val);return f[0][1].cnt >= K + 1;
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d %d", &N, &K);for(int i = 1; i < N; i++) {
    int u, v, w;scanf("%d %d %d", &u, &v, &w);addedge(u, v, w);}ll lb = -INF, ub = INF;while(lb <= ub) {
    ll mid = (lb + ub) >> 1;if(check(mid)) lb = mid + 1;else ub = mid - 1;}check(lb);ll ans = f[0][1].val + 1LL * lb * (K + 1);printf("%lld\n", ans);return 0;
}