注意一下数组更新的顺序就行了
代码 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define rg register inline int read(){ rg int x=0,fh=1; rg char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') fh=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*fh; } const int maxn=3e5+5; typedef long long ll; int h[maxn],tot=1,n,k; struct asd{ int to,nxt,val; }b[maxn<<1]; void ad(rg int aa,rg int bb,rg int cc){ b[tot].to=bb; b[tot].nxt=h[aa]; b[tot].val=cc; h[aa]=tot++; } struct jie{ int cnt; ll val; jie(){} jie(rg int aa,rg ll bb){ cnt=aa,val=bb; } friend jie operator + (const jie& A,const jie& B){ return jie(A.cnt+B.cnt,A.val+B.val); } friend bool operator < (const jie& A,const jie& B){ if(A.val==B.val) return A.cnt<B.cnt; return A.val<B.val; } }f[maxn][3]; jie Max(rg jie aa,rg jie bb){ return aa<bb?bb:aa; } void dfs(rg int now,rg int lat,rg ll val){ f[now][1]=f[now][0]=jie(0,0); f[now][2]=jie(1,val); for(rg int i=h[now];i!=-1;i=b[i].nxt){ rg int u=b[i].to; if(u==lat) continue; dfs(u,now,val); f[now][2]=Max(f[now][2]+f[u][0],f[now][1]+f[u][1]+jie(1,b[i].val+val)); f[now][1]=Max(f[now][0]+f[u][1]+jie(0,b[i].val),f[now][1]+f[u][0]); f[now][0]=Max(f[now][0],f[now][0]+f[u][0]); } f[now][0]=Max(f[now][0],Max(f[now][2],f[now][1]+jie(1,val))); } void init(){ for(rg int i=1;i<=n;i++){ f[i][0].cnt=f[i][1].cnt=f[i][2].cnt=0; f[i][0].val=f[i][1].val=f[i][2].val=-0x3f3f3f3f3f3f3f3f; } } int main(){ memset(h,-1,sizeof(h)); n=read(),k=read(); rg int aa,bb,cc; for(rg int i=1;i<n;i++){ aa=read(),bb=read(),cc=read(); ad(aa,bb,cc); ad(bb,aa,cc); } k++; rg long long l=-3e11,r=3e11,mids,ans; while(l<=r){ mids=(l+r)>>1; init(); dfs(1,0,mids); if(f[1][0].cnt<k){ l=mids+1; } else { ans=f[1][0].val-1LL*mids*k; r=mids-1; } } printf("%lld\n",ans); return 0; }