LuoguP4383 [八省联考2018]林克卡特树lct
https://www.luogu.org/problemnew/show/P4383
分析:
- 题意等价于选择\(K\)条点不相交的链，使得总路径长度和最大。
- 设\(f[x][i][0/1/2]\)表示\(x\)子树中选了\(i\)个，\(x\)的当前度数为\(0/1/2\)的答案。
- 然后我们感性理解一下可知，选\(k\)个点的方案，一定能够从\(k-1\)个点的方案中转移过来的，不会出现从\(k-i(i>1)\)上再选若干个不在\(k-1\)的方案中的链转移过来答案更优。
- 那么由于我们选择的链的权值是不断变小的，可知\(dp\)值是个凸函数，且单峰。
- 使用带权二分即可，对于本题，整数二分就可以通过。
代码:
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300050
typedef long long ll;
const ll inf = 1ll<<60;
int head[N],to[N<<1],nxt[N<<1],cnt,val[N<<1],n,K,siz[N];
// ll f[N][105][3],tmp[105][3];
struct A {
ll x; int k;
A() {}
A(ll x_,int k_) {x=x_, k=k_;}
bool operator < (const A &u) const {
return x==u.x ? k>u.k : x<u.x;
}
A operator + (const A &u) const {
return A(x+u.x, k+u.k);
}
}f[N][3],ans,tmp[3];
inline void add(int u,int v,int w) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
template<typename T>void chkmax(T &x,T y) {if(x<y)x=y;}
template<typename T>void chkmin(T &x,T y) {if(y<x)x=y;}
ll C;
// void dfs(int x,int y) {
// int i,j,k,p,q; siz[x]=1;
// memset(f[x],0xc0,sizeof(f[x]));
// f[x][0][0]=f[x][1][2]=0;
// for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {
// dfs(to[i],x);
// for(j=0;j<=K&&j<=siz[x];j++) for(k=0;k<3;k++) tmp[j][k]=f[x][j][k], f[x][j][k]=-inf;
// int t=to[i],len=val[i];
// for(j=0;j<=K&&j<=siz[x];j++) {
// for(k=0;k<=K-j+1&&k<=siz[to[i]];k++) {
// //not choose
// for(p=0;p<3;p++) for(q=0;q<3;q++) chkmax(f[x][j+k][p],tmp[j][p]+f[t][k][q]);
// //choose
// chkmax(f[x][j+k+1][1],tmp[j][0]+f[t][k][0]+len);
// chkmax(f[x][j+k][1],tmp[j][0]+f[t][k][1]+len);
// chkmax(f[x][j+k][2],tmp[j][1]+f[t][k][0]+len);
// chkmax(f[x][j+k-1][2],tmp[j][1]+f[t][k][1]+len);
// }
// }
// siz[x]+=siz[to[i]];
// }
// }
void dfs(int x,int y) {
int i,p,q;
f[x][0]=A(0,0); f[x][1]=A(-inf,0); f[x][2]=A(C,1);
for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {
int t=to[i];
dfs(to[i],x);
memcpy(tmp,f[x],sizeof(f[x]));
f[x][0]=f[x][1]=f[x][2]=A(-inf,0);
//not choose
for(p=0;p<3;p++) for(q=0;q<3;q++) chkmax(f[x][p],tmp[p]+f[t][q]);
chkmax(f[x][1],tmp[0]+f[t][0]+A(val[i]+C,1));
chkmax(f[x][1],tmp[0]+f[t][1]+A(val[i],0));
chkmax(f[x][2],tmp[1]+f[t][0]+A(val[i],0));
chkmax(f[x][2],tmp[1]+f[t][1]+A(val[i]-C,-1));
}
}
int main() {
scanf("%d%d",&n,&K);
K++;
int i,x,y,z;
for(i=1;i<n;i++) {
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
// dfs(1,0);
// printf("%lld\n",max(max(f[1][K][0],f[1][K][1]),f[1][K][2]));
ll l=-1e9, r=1e9;
while(l<r) {
ll mid=(l+r)>>1;
C=mid; dfs(1,0);
ans=max(max(f[1][0],f[1][1]),f[1][2]);
if(ans.k>K) r=mid;
else if(ans.k==K) {
printf("%lld\n",ans.x-K*C); return 0;
}
else l=mid+1;
}
l--;
C=l; dfs(1,0);
ans=max(max(f[1][0],f[1][1]),f[1][2]);
printf("%lld\n",ans.x-K*C);
}