【BZOJ5252】林克卡特树（动态规划，凸优化）

题面

BZOJ(交不了)

洛谷

题解

这个东西显然是随着断开的越来越多，收益增长速度渐渐放慢。

所以可以凸优化。

考虑一个和\(k\)相关的\(dp\)

这个题目可以转换为在树上选择\(K\)条不相交的路径。

设\(f[i][0/1/2]\)表示当前点\(i\)，这个点不和父亲连/和父亲连/在这里将两条链合并的最优值。

再记一维\(k\)，表示子树中已经选了\(k\)条链。

这样子可以直接转移。

那么凸优化\(dp\)，再额外记录一下最优解的链的最小值，就好了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define MAX 300300

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next,w;}e[MAX<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

ll sum;

int n,K;

struct Node{ll x;int y;}f[3][MAX],ans;

bool operator<(Node a,Node b){if(a.x!=b.x)return a.x<b.x;return a.y>b.y;}

Node operator+(Node a,Node b){return (Node){a.x+b.x,a.y+b.y};}

void cmax(Node &a,Node b){a=a<b?b:a;}

void dfs(int u,int ff,ll mid)

{

	f[0][u]=(Node){0,0};

	f[1][u]=(Node){-mid,1};

	f[2][u]=(Node){-1ll<<60,0};

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(v==ff)continue;

		dfs(v,u,mid);

		Node tmp=max(f[0][v],max(f[1][v],f[2][v]));

		cmax(f[2][u],f[2][u]+tmp);

		cmax(f[2][u],f[1][u]+f[1][v]+(Node){e[i].w+mid,-1});

		cmax(f[1][u],f[1][u]+tmp);

		cmax(f[1][u],f[0][u]+f[1][v]+(Node){e[i].w,0});

		cmax(f[1][u],f[0][u]+f[0][v]+(Node){-mid,1});

		cmax(f[0][u],f[0][u]+tmp);

	}

	cmax(ans,max(f[0][u],max(f[1][u],f[2][u])));

}

int main()

{

	n=read();K=read()+1;

	for(int i=1;i<n;++i)

	{

		int u=read(),v=read(),w=read();

		Add(u,v,w);Add(v,u,w);sum+=abs(w);

	}

	ll l=-sum,r=sum;

	while(l<r)

	{

		ll mid=(l+r)>>1;

		ans=(Node){-1ll<<60,0};dfs(1,0,mid);

		if(ans.y>K)l=mid+1;

		else r=mid;

	}

	ans=(Node){-1ll<<60,0};dfs(1,0,r);

	printf("%lld\n",r*K+ans.x);

	return 0;

}