Chlience

【题解】LOJ 2478 「九省联考 2018」林克卡特树
Problem我会告诉你我看了好久都没发现这是求 $k+1$ 不相交路径最大值么?Thought这种东西一般来说是...
扫描右侧二维码阅读全文
06
2019/01

【题解】LOJ 2478 「九省联考 2018」林克卡特树

Problem

我会告诉你我看了好久都没发现这是求 $k+1$ 不相交路径最大值么?

Thought

这种东西一般来说是一个和 $k$ 相关的凸函数(斜率不降),所以可以用 $DP$ 凸优化

接下来就是考虑 $DP$ 过程

每个点设三个状态 $f[x][0,1,2]$ 表示其在子树中的度数

考虑每个状态的转移:

若当前点 $x$ 连接了其儿子节点 $t$,则

$f[x][2]=f[x][1]+f[t][1]+e[i].w+cost$

$f[x][1]=f[x][0]+f[t][1]+e[i].w$

若当前点 $x$ 没有连接其儿子节点 $t$,则

$f[x][0]=f[x][0]+max(f[t][0,1,2])$

$f[x][1]=f[x][1]+max(f[t][0,1,2])$

$f[x][2]=f[x][2]+max(f[t][0,1,2])$

为什么在连接时不考虑连接 $f[t][0]$ 呢?因为 $f[t][0]$ 和 $f[t][1]$ 仅仅是因为是否有连接了一个子树作为区分,而 $f[t][1]$ 的初始状态和 $f[t][0]$ 相等,显然是不会比 $f[t][0]$ 更差的,所以说直接通过 $f[t][1]$ 转移即可

至于为啥要加 $cost$ ,是因为在 $f[x][1],f[t][1]$ 处减少了两次 $cost$ ,这里合为一条链就要加回来,链条数同理

Code

#include <bits/stdc++.h>
using namespace std;
#define mid ((L + R) >> 1ll)
typedef long long ll;
const int N = 300010;
int n , k;
ll L , R , cost;
struct Node {
    ll a; int b;
    Node() {}
    Node(ll _a , int _b) {a = _a; b = _b;}
    bool operator < (const Node x) const {
        if(a == x.a) return b > x.b;
        return a < x.a;
    }
}f[N][3];
Node operator + (Node x , Node y) {return Node(x.a + y.a , x.b + y.b);}
struct Edge {int t , n , w;}e[N << 1];
int head[N] , tot;

int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
void addedge(int u , int v , int w) {
    e[++ tot] = {v , head[u] , w};
    head[u] = tot;
}
void dfs(int x , int fa) {
    f[x][0] = {0 , 0};
    f[x][1] = f[x][2] = {- cost , 1};
    for(int i = head[x] ; i ; i = e[i].n) {
        int t = e[i].t;
        if(t == fa) continue;
        dfs(t , x);
        Node maxval = max(f[t][0] , max(f[t][1] , f[t][2]));
        Node t2 = max(f[x][1] + f[t][1] + Node(e[i].w + cost , - 1) , f[x][2] + maxval);
        f[x][2] = max(f[x][2] , t2);
        Node t1 = max(f[x][0] + f[t][1] + Node(e[i].w , 0) , f[x][1] + maxval);
        f[x][1] = max(f[x][1] , t1);
        f[x][0] = max(f[x][0] , f[x][0] + maxval);
    }
}
int main() {
    n = read(); k = read() + 1;
    for(int i = 1 ; i < n ; ++ i) {
        int u = read() , v = read() , w = read();
        addedge(u , v , w); addedge(v , u , w);
        R += max(0 , w); L = min(L , - 1ll * w);
    }
    while(L < R) {
        cost = mid;
        dfs(1 , 0);
        Node t = max(f[1][0], max(f[1][1], f[1][2]));
        if(t.b <= k) R = mid;
        else L = mid + 1ll;
    }
    cost = L;
    dfs(1 , 0);
    Node t = max(f[1][0], max(f[1][1], f[1][2]));
    printf("%lld\n" , t.a + L * k);
    return 0;
}
Last modification:January 6th, 2019 at 05:06 pm

Leave a Comment