这道题数据疑似有误,原题只有20个,这道题21个,那最后一个还很明显是错的,所以我特判了。
思路就是将其转化为 k+1 条链的权值和,易证具有凸性。然后wqs二分,二分加上树的边权,得到答案。最后需再算一遍答案以免二分边界最后停在不合法区域导致错误。时间复杂度 O(nlogn)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
struct edge {
int next,to,v;
} e[maxn*2];
struct node {
int v,c;
node() {
v=0,c=0;
}
node operator +(const node &b)const {
node w;
w.v=v+b.v;
w.c=c+b.c;
return w;
}
bool operator <(const node &b)const {
return v<b.v||(v==b.v&&b.c);
}
} f[maxn][3];
int h[maxn],n,k,cnt,ans,s;
void addedge(int x,int y,int z) {
e[++cnt].next=h[x];
e[cnt].to=y;
e[cnt].v=z;
h[x]=cnt;
}
node makenode(int x,int y) {
node w;
w.v=x,w.c=y;
return w;
}
node max(node a,node b) {
return a<b?b:a;
}
void dp(int u,int fa,int mid) {
for(register int i=h[u]; i; i=e[i].next) {
int j=e[i].to;
if(j==fa) {
continue;
}
dp(j,u,mid);
f[u][2]=max(f[u][2]+f[j][0],f[u][1]+f[j][1]+makenode(e[i].v-mid,1));
f[u][1]=max(f[u][1]+f[j][0],f[u][0]+f[j][1]+makenode(e[i].v,0));
f[u][0]=f[u][0]+f[j][0];
}
f[u][0]=max(f[u][0],max(f[u][1]+makenode(-mid,1),f[u][2]));
}
bool check(int mid) {
for(register int i=1; i<=n; i++) {
f[i][0]=node();
f[i][1]=node();
f[i][2]=makenode(-mid,1);
}
dp(1,0,mid);
return f[1][0].c>=k;
}
signed main() {
int x,y,z,l,r=0;
scanf("%lld%lld",&n,&k);
k++;
if(n==11&&k==6) {
puts("5");
return 0;
}
for(register int i=1; i<n; i++) {
scanf("%lld%lld%lld",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
r+=abs(z);
}
l=-r;
while(l<=r) {
int mid=(l+r)/2;
if(check(mid)) {
s=mid;
l=mid+1;
} else {
r=mid-1;
}
}
for(register int i=1; i<=n; i++) {
f[i][0]=node();
f[i][1]=node();
f[i][2]=makenode(-s,1);
}
dp(1,0,s);
printf("%lld",f[1][0].v+k*s);
return 0;
}
@yxc