萌新求调 wqs 二分

RT。感觉是 DP 的锅。

思路大概是设 f_{x,i\in[0,2]} 为 x 与儿子 连了 i 条边的时候，x 子树中最大贡献和。

对于 wqs 二分的权值加在每条链的 LCA，即 f_{x,1} 向父亲转移且不链这条边时和 f_{x,2} 合并两条链时。

只有 65 分，单点为链的情况也考虑了，不知道哪里错了，请教各位大佬。

值得一提的是如果我把注释上面那一行换成注释那一行的话，就有 75 分，但是我并不认为应该那样写。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN=3e5+10,MAXM=6e5+10,INF=1e18;
int to[MAXM],nxt[MAXM],head[MAXN],val[MAXM],cnt;
inline void add(int x,int y,int v)
    {to[++cnt]=y,nxt[cnt]=head[x],val[head[x]=cnt]=v;}
typedef pair<int,int> P;
int n,m,k;P f[MAXN][3];
inline P operator + (const P x,const P y)
    {return (P){x.first+y.first,x.second+y.second};}
inline P operator - (const P x,const P y)
    {return (P){x.first-y.first,x.second-y.second};}
struct set
{
    P a,b;inline void insert(P now)
    {if(now>a) swap(now,a);if(now>b) swap(now,b);}
}s[MAXN];
P calc(int y)
{
    P MAX=max(max(f[y][0],f[y][2]),f[y][1]+(P){k,1});
    return max(MAX,(k>=0)?(P){k,1}:(P){0,0});
}
void dfs(int x,int fa=0)
{
    s[x].a=s[x].b={-INF,-INF},f[x][0]={0,0};
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];if(y==fa) continue;dfs(y,x);
        P MAX=calc(y);f[x][0]=f[x][0]+MAX;
        s[x].insert(max(max(f[y][0],f[y][1]),(P){0,0})+(P){val[i],0}-MAX);
        // s[x].insert(max(max(f[y][0],f[y][1]),max((P){0,0},(P){k,1}))+(P){val[i],0}-MAX);
    }
    f[x][1]=f[x][0]+s[x].a;
    f[x][2]=f[x][0]+s[x].a+s[x].b+(P){k,1};
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;for(int i=1,x,y,v;i<n;++i)
        cin>>x>>y>>v,add(x,y,v),add(y,x,v);
    int L=-1e12-10,R=+1e12+10;while(L<R)
    {
        int mid=(L+R)>>1;k=mid;
        dfs(1);P ans=calc(1);
        (ans.second<m+1)?L=mid+1:R=mid;
    }
    k=L;dfs(1);P ans=calc(1);
    cout<<ans.first-L*(m+1)<<'\n';return 0;
}