PLCT检查是什么[八省联考2018]林克卡特树lct——WQS二分

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x)
namespace Miracle{
const int N=3e5+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,k;
int b[N][3];
struct node{
    int nxt,to;
    ll val;
}e[2*N];
int hd[N],cnt;
void add(int x,int y,ll z){
    e[++cnt].nxt=hd[x];
    e[cnt].val=z;
    e[cnt].to=y;
    hd[x]=cnt;
}
struct dp{
    ll v;
    int c;
    dp(){}
    dp(ll a,int b){
        v=a;c=b;
    }
    dp operator +(const dp &b){
        return dp(v+b.v,c+b.c);
    }
    bool friend operator <(dp a,dp b){
        return (a.v<b.v||(a.v==b.v&&a.c<b.c));
    }
    void clear(){
        v=-inf;c=-0x3f3f3f3f;
    }
}f[N][3];
ll sum;
void dfs(int x,int fa,ll mid)
    f[x][1]=max(f[x][1],f[x][0]+dp(-mid,1));
    f[x][0]=max(f[x][0],max(f[x][1],f[x][2]));
}
int check(ll mid)
    dfs(1,0,mid);
//    for(reg i=1;i<=n;++i){
//        cout<<" i "<<i<<" : "<<f[i][0].v<<" "<<f[i][0].c<<endl;
//    } 
    sum=f[1][0].v;
//    cout<<" mid "<<mid<<" :: "<<sum<<" "<<f[1][0].c<<endl;
    return f[1][0].c;
}
int main(){
    rd(n);rd(k);
    ++k;
    ll l=0,r=0;
    for(reg i=1;i<n;++i){
        rd(b[i][0]);rd(b[i][1]);rd(b[i][2]);
        r+=abs(b[i][2]);
    }l=-r;
    ll ans=-233;
    while(l<=r)
    int haha=check(ans);
    printf("%lld
",sum+(ll)k*ans);
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2019/2/20 15:23:18
*/