luoguP4383 [八省联考2018]林克卡特树(树上dp，wqs二分)
题解时间
$ k $ 条边权为 $ 0 $ 的边。
是的，边权为零。
转化成选正好 $ k+1 $ 条链。
$ k le 100 $ 的部分。
毫无疑问是树上打背包dp。
但具体设计还要注意一下。
一个问题是单点成链，这个要特判。
之后由于选择的都是链，所以每个点的度数不会超过2.
这样方程就出来了。
$ k le n $ 的部分。
很明显不能背包了。
但“选正好k个求最大权值和”这个要求如果熟悉的话可能想到wqs二分。
打表试一下发现确实是上凸函数。
之后就按wqs二分的套路来，二分加权mid，求 $ dp_{x,k,deg} - mid * k $ 就完事了。
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
template<typename TP>inline void read(TP &tar)
{
TP ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}
tar=ret*f;
}
namespace RKK
{
const int N=300011;
const int inf=0x3f3f3f3f;
const lint linf=0x3f3f3f3f3f3f3f;
struct sumireko{int to,ne;lint w;}e[N<<1];int he[N],ecnt;
void addline(int f,int t,lint w){e[++ecnt].to=t,e[ecnt].w=w;e[ecnt].ne=he[f],he[f]=ecnt;}
struct pat
{
lint v,k;pat(lint v=-linf,lint k=inf):v(v),k(k){}
bool operator<(const pat &p)const{return v==p.v?k>p.k:v<p.v;}
pat friend operator+(const pat &pa,const pat &pb){return pat(pa.v+pb.v,pa.k+pb.k);}
}dp[N][3],dg[3],dtmp;
int n,kap;lint km;
void dfs(int x,int f)
{
for(int i=he[x],t=e[i].to,w=e[i].w;i;i=e[i].ne,t=e[i].to,w=e[i].w)if(t!=f)
{
dfs(t,x);for(int p=0;p<3;p++) dg[p]=pat();
for(int j=0;j<3;j++)for(int p=0;p<3;p++) dg[j]=max(dg[j],dp[x][j]+dp[t][p]);
dg[1]=max(dg[1],dp[x][0]+max(dp[t][0]+pat(w-km,1),dp[t][1]+pat(w,0)));
dg[2]=max(dg[2],dp[x][1]+max(dp[t][0]+pat(w,0),dp[t][1]+pat(w+km,-1)));
memcpy(dp[x],dg,sizeof(dg));
}
}
void dpclr(){for(int i=1;i<=n;i++) dp[i][0]=pat(0,0),dp[i][1]=pat(),dp[i][2]=pat(-km,1);}
int main()
{
#ifdef RDEBUG
freopen("sample.in","r",stdin);
#endif
read(n),read(kap),kap++;for(int i=2,x,y,w;i<=n;i++) read(x),read(y),read(w),addline(x,y,w),addline(y,x,w);
lint ql=-1e8,qr=1e8,qm,qa;
while(ql<=qr)
{
qm=ql+qr>>1,km=qm;
dpclr(),dfs(1,0),dtmp=max(dp[1][0],max(dp[1][1],dp[1][2]));
if(dtmp.k==kap){printf("%lld
",dtmp.v+km*kap);return 0;}
else if(dtmp.k>kap) ql=qm+1;
else qr=qm-1,qa=qm;
}
km=qa;
dpclr(),dfs(1,0),dtmp=max(dp[1][0],max(dp[1][1],dp[1][2]));
printf("%lld
",dtmp.v+km*kap);
return 0;
}
}
int main(){return RKK::main();}