P4383-[八省聯考2018]林克卡特樹【wqs二分,樹形dp】

正題

題目連結:https://www.luogu.com.cn/problem/P4383

題目大意

\(n\)個點的一棵樹，要求删除\(k\)條邊然後接上\(k\)條邊權為\(0\)的邊後形成的樹上選擇一對\((p,q)\)從\(p\)走簡單路徑到\(q\)的權值和最大。

\(n,k\leq 3\times 10^5\)

解題思路

其實可以了解為選恰好\(k+1\)條不相交的路徑（可以選擇一個點）使得權值和最大，這樣删除路徑最頂部的那條邊一定有方案構造。

因為是恰好選擇，是以考慮\(wqs\)二分，給每條路徑加上一個權值\(mid\)，然後考慮用樹形\(dp\)做就很簡單了。設\(f_{i,0/1/2}\)表示\(i\)号點沒有路徑經過/在路徑之間/作為路徑頂部時子樹内的最小權值，然後轉移即可。

時間複雜度：\(O(n\log W)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=3e5+10;
struct edge{
	ll to,next,w;
}a[N<<1];
struct node{
	ll w,g;
}f[N][3];
ll n,k,tot,c,ls[N];
node operator+(node x,node y)
{return (node){x.w+y.w,x.g+y.g};}
node operator+(node x,ll y)
{return (node){x.w+y,x.g};}
node operator^(node x,ll y)
{return (node){x.w,x.g+y};}
node mx(node x,node y){
	if(x.w==y.w)return (x.g>y.g)?x:y;
	return (x.w>y.w)?x:y;
}
void addl(ll x,ll y,ll w){
	a[++tot].to=y;
	a[tot].next=ls[x];
	a[tot].w=w;ls[x]=tot;
	return;
}
void dfs(ll x,ll fa){
	f[x][0]=f[x][1]=(node){0,0};f[x][2]=(node){c,1};
	for(ll i=ls[x];i;i=a[i].next){
		ll y=a[i].to;
		if(y==fa)continue;dfs(y,x);
		f[x][2]=mx(f[x][2]+f[y][0],(f[x][1]+f[y][1]+a[i].w+c)^1);
		f[x][1]=mx(f[x][0]+f[y][1]+a[i].w,f[x][1]+f[y][0]);
		f[x][0]=f[x][0]+f[y][0];
	}
	f[x][0]=mx(f[x][0],mx((f[x][1]+c)^1,f[x][2]));
	return;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	ll sum=0;k++;
	for(ll i=1;i<n;i++){
		ll x,y,w;
		scanf("%lld%lld%lld",&x,&y,&w);
		addl(x,y,w);addl(y,x,w);sum+=abs(w);
	}
	ll l=-sum,r=sum;
	while(l<=r){
		ll mid=(l+r)>>1;
		c=mid;dfs(1,0);
		if(f[1][0].g<k)l=mid+1;
		else r=mid-1;
	}
	c=l;dfs(1,0);
	printf("%lld\n",f[1][0].w-c*k);
	return 0;
}