题解 P4383 【[八省联考2018]林克卡特树lct】

· · 题解

dp凸优化/wqs二分/带权二分

这里可能会给出一个(我大力口胡的)对于这类算法正确性的证明，并且会涉及到对于边界情况的处理

本题题解

题意

给你一棵树，割掉恰好k条边然后重新接上恰好k条0权边，然后要求最大化新树的直径

割掉k条边之后会出现k+1个联通块，那么我们对于每一个联通块求直径然后用k条边将这k个联通块串起来即可了

所以问题变成了在树上寻找k+1条点不相交链，并且最大化这k+1条链的边权之和

注意，一个点被视作退化的一条链

一看又是乱七八糟的树上最优化问题，不是树分治就是树形dp

似乎树分治处理多条路径的时候能力有限……，所以我们基本断定是个树形dp

按照树形dp的无脑套路，Dp_{i,j}表示链全部在i的子树中，一共有j条链时这些链的最大边权和

那么我们按照树形dp的转移思路就是考虑“拼合”最高点为u和最高点为v这两个子联通块

问题来了，我们突然意识到这个状态似乎无法转移……

情况突然变得尴尬……

冷静分析一下会发现没有办法转移的关键是无法拼合两条路径

因为有些时候两个联通块拼到一起会将两个路径拼成一个路径，此时我们根据dp数组中的状态并无法还原这种情况

观察到是点不相交的路径，因此我们发现一件事，在最后的选中的链构成图形中，一个点的度数至多为2

所以额外补上一维k,k\in \{0,1,2\}表示点i的度数

此时我们考虑将最高点为u和最高点为v的两个联通块拼到一起，那么转移方式就是枚举u,v之间的边是否出现在这k条链当中

然后我们手动分情况讨论一波转移

case 1:u,v之间的边不选

那么点u的度数不变，然后路径条数为两个联通块的路径条数之和，然后dp值就是两个状态的dp值简单相加

case 2:u,v之间的边被选择

需要注意的是，如果u和v之间有一个的度数是2那么这个转移就是非法的

那么点u的度数如果是1那么变成2，如果是0变成1，dp值是两个状态的dp值简单相加，再加上u到v的边权，路径条数在两个点的点度都是0的时候总路径条数+1，两个点的点度都是1的时候发现拼合了一条路径，总路径条数-1，两个点的点度有一个是0另一个是1的时候由于相当于延长了一个路径所以说路径条数不变

然后我们就可以写出一个复杂度O(nk)的暴力了

边界条件呢?

Dp_{i,0,0}=0

其他值初始化为- \infty

听起来很有道理？

然后你发现你忘记了一种情况……

注意，一个点被视作退化的一条链

这样dp是dp不出来只有一个点的路径的……

所以我们稍稍给边界条件动一动手脚，将只有一个点的路径视为一个自环，那么这个点的度数就为2，或者你可以简单的认为这个点成为单独的一个路径之后就无法和其他的路径相拼接。

所以稍稍fix下边界条件

Dp_{i,0,0}=0,Dp_{i,1,2}=0

其他值初始化为 - \infty

然后我们就可以愉快的dp了，答案是max(Dp_{1,k,0},Dp_{i,k,1},Dp_{i,k,2})

然后我们会发现除了暴力dp之外似乎没什么做法了

套用官方题解中的一句话，假设你是一名秒出dp，即将ak的julao，闲来无事的时候的打印了k=0~100的所有答案，你会惊奇的发现这个函数是一个上凸函数/差分单调递减

所以下面就是这道题需要的技巧了——dp凸优化/wqs二分

Dp凸优化

假设我们有一个很难求的函数f(x)我们知道它是一个凸函数，换句话说导函数/差分单调

我们还有一个性质，函数G(x,k)=f(x)-kx的极值非常好算(但是G(x)的任意点值同样难算)，并且我们不仅可以知道G(x,k)的极值，而且我们还知道取极值的时候x的值

那么此时我们计算F(n)的值是有一个快速方法的

具体来讲是这样，我们设函数G(x,k)的极值为C,且取最大值时x的取值是t

G(t,k)=f(t)-tx=C

f(t)=tx+C

等一下……我们毫不费力的计算出了F(t)的值

换句话说，点(t,f(t))在y=kx+C这条直线上

又因为对于其他不是t的点p有

G(p,k)=f(p)-kp \leq C

f(p) \leq kp+C

因此，我们会发现函数F(x)的图像应该在直线y=kx+C的下方，且t一定是两个函数类似于一个切点之类的东西(因为两个函数可能有多个交点)

刚才说过如果我们十分幸运的猜中了一个k使得G(x,k)在x==n时取得极值的话，我们就可以计算出f(n)的值

当然现实是我们没有那么幸运……

但是我们会发现一个十分微妙的事实是随着k的增大函数G(x,k)的极值点向右/左单调的移动

这当然不是什么奇怪的性质而是因为这样一个简单的事实，函数F(x)是凸的

所以极值点自然是差分取0时的点

而函数G(x,k)=f(x)-kx相当于是f(x)的差分减k之后形成的函数

所以极值点(差分0点)自然就是随着k的增加而单调的了

既然有单调性我们就可以二分斜率k，然后每次求出极值点的位置和n进行比较，然后我们按照我们的需求对于k进行调整，直到我们的极值点恰好是n，于是我们就顺理成章的求出了f(n)的值

做完了?

听起来好像没什么毛病……

有一个问题。

函数G(x,k)的极值点不一定唯一

这意味着我们将没有办法判断n到底是在极值点的左边还是右边

但是还好F(x)是凸的，所以我们有一个性质可以用，那就是函数G(x,k)的所有极值点构成一个连续区间，而不会有多个区间，具体来讲就是你的斜率k和凸函数的一段斜率是一样的，于是你的直线和凸函数有一条边重合而不是一个点重合了

另一个好消息是这段区间内的点都可以使用刚才的手法(kx+c)计算出对应的f(x)值，因为这个凸函数和直线重合

所以我们的问题变成了求点n所在直线的斜率

那么我们只需对刚才的二分稍加修改即可解决这个问题，我们求极值点的时候增加一个限制，如果有多个极值点，那么我们求最小的那一个，然后进行比较继续二分，注意的是边界条件的处理，我们应保证最后二分到底的时候，如果斜率k对应的极值点不等于n的话，这个极值点应该比n要小

此时我们发现，如果极值点t不等于n的话，那么(n,f(n))和(t,f(t))在同一条直线上，所以直接将n带入t所在的直线即可计算出f(n)

好了回到刚才的问题

我们有一个很难求的函数f(x)=max(Dp_{1,x,0},Dp_{1,x,1},Dp_{1,x,2})

现在我们想要求f(n)

而函数G(x,k)=f(x)-kx这个东西可以在O(n)时间内求出

具体来讲你把转移方程第二维去掉，然后在生成/拼合一条路径时减去/加上对应的k就好了

还要支持求极值点，如果有多个相同的极值点，应该求出最小的，这个也好办，你的dp数组写一个结构体，给小于号做做手脚，到时候直接max就好了

至此问题完全转化为刚才的问题，求出(n,f(n))所在的直线方程直接代入求值即可

注意一个小坑，(l+r)/2不等于\lfloor \frac{l+r}{2} \rfloor,所以手动实现一下下取整

另外inf设大一点，因为这题的数值范围较大……

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=3*1e5+10;typedef long long ll;
int v[2*N];int x[2*N];int ct;int al[N];ll val[2*N];bool book[N];int n;int k;
inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;}
struct data//dp的结构体 
{
    ll v;int k;
    friend bool operator <(data a,data b){return (a.v==b.v)?a.k>b.k:a.v<b.v;}//重载< 
    friend data operator +(data a,data b){return (data){a.v+b.v,a.k+b.k};}
}dp[N][3];data tr[3];ll mid;
inline void dfs(int u)//树形dp 
{
    book[u]=true;
    for(int i=al[u];i;i=x[i])
    {
        if(book[v[i]])continue;dfs(v[i]);ll va=val[i];
        for(int j=0;j<3;j++)tr[j]=(data){-0x7f7f7f7f7f,0x3f3f3f3f};
        for(int j=0;j<3;j++)tr[0]=max(tr[0],dp[u][0]+dp[v[i]][j]);
        tr[1]=max(tr[1],dp[u][0]+dp[v[i]][0]+(data){va-mid,1});
        tr[1]=max(tr[1],dp[u][0]+dp[v[i]][1]+(data){va,0});
        for(int j=0;j<3;j++)tr[1]=max(tr[1],dp[u][1]+dp[v[i]][j]);
        tr[2]=max(tr[2],dp[u][1]+dp[v[i]][0]+(data){va,0});
        tr[2]=max(tr[2],dp[u][1]+dp[v[i]][1]+(data){va+mid,-1});
        for(int j=0;j<3;j++)tr[2]=max(tr[2],dp[u][2]+dp[v[i]][j]);
        for(int j=0;j<3;j++)dp[u][j]=tr[j];
    }book[u]=false;
}
inline void ih()//初始化边界条件 
{
    for(int i=1;i<=n;i++)
        dp[i][0]=(data){0,0},dp[i][1]=(data){-0x7f7f7f7f7f,0x3f3f3f3f},
        dp[i][2]=(data){-mid,1};
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1,u,v,va;i<n;i++){scanf("%d%d%d",&u,&v,&va);add(u,v,va);add(v,u,va);}
    ll l=-1e12;ll r=1e12;
    while(l!=r)
    {
        mid=(double)(l+r)/2-0.5;ih();dfs(1);
        data jud=max(dp[1][0],max(dp[1][1],dp[1][2]));
        if(jud.k==(k+1)){printf("%lld",jud.v+(k+1)*mid);return 0;}
        if(jud.k>(k+1)){l=mid+1;}else r=mid;//二分斜率 
    }mid=l;ih();dfs(1);data jud=max(dp[1][0],max(dp[1][1],dp[1][2]));
    printf("%lld",jud.v+(k+1)*mid);return 0;//带入直线方程求值 
}