F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 5252 >> 新人求助,5252题,本机&洛谷&jzoj ac,bzoj wa。
ltsb1 @ 2019-08-07 22:09:55
[ Quote ] [ Edit ] [ Delete ] 1#
以下是我的代码:
#include<bits/stdc++.h>
using namespace std;
#define N 300010
typedef long long ll;
int n,k,v[N*2],nxt[N*2],ec;
struct no{
ll x,c;
}f[N][3];
ll w[N*2],h[N];
no operator +(no x,no y){
return (no){x.x+y.x,x.c+y.c};
}
int operator <(no x,no y){
return x.x<y.x||(x.x==y.x&&x.c>y.c);
}
no operator +(no x,ll v){x.x+=v;return x;}
void add(int x,int y,ll z){v[++ec]=y;w[ec]=z;nxt[ec]=h[x];h[x]=ec;}
no up(no x,ll v){return(no){x.x-v,x.c+1ll};}
void dp(int x,int fa,ll va){
for(int i=h[x];i;i=nxt[i])
if(v[i]!=fa){
dp(v[i],x,va);
f[x][2]=max(f[x][2]+f[v[i]][0],up(f[x][1]+f[v[i]][1]+w[i],va));
f[x][1]=max(f[x][1]+f[v[i]][0],f[v[i]][1]+f[x][0]+w[i]);
f[x][0]=f[x][0]+f[v[i]][0];
}
f[x][0]=max(f[x][0],max(up(f[x][1],va),f[x][2]));
}
int main(){
scanf("%d%d",&n,&k);k++;
for(int i=1;i<n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
ll l=-1e12,r=1e12;
while(l<=r){
ll md=(l+r)>>1;
memset(f,0,sizeof(f));
dp(1,0,md);
if(f[1][0].c<=k)r=md-1;else l=md+1;
}
memset(f,0,sizeof(f));
dp(1,0,l);printf("%lld\n",l*k+f[1][0].x);
}
ltsb1 @ 2019-08-07 22:10:36
[ Quote ] [ Edit ] [ Delete ] 2#
md,我忘了这题1s时限,做不了。。。。
[Top] [Previous Page] [Next Page]

HOME Back