[NOIP2018TG]赛道修建

考场上multiset调不出啊啊啊!!!

首先肯定是二分答案

做树形dp,f[i]表示i点的子树两两匹配后剩下的最长长度

匹配可以用multiset维护

但是菊花图跑得很慢

考虑求出树的直径作为二分上界

#include<bits/stdc++.h>

using namespace std;

const int _=5e4+5;

int re(){

    int x=0,w=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*w;

}

int n,m,cnt,t,l,r,mid,tot,ans;

int h[_],f[_];

multiset<int>s[_];

multiset<int>::iterator it,ir;

struct edge{int to,next,w;}e[_<<1];

void link(int u,int v,int w){

    e[++cnt]=(edge){v,h[u],w};h[u]=cnt;

    e[++cnt]=(edge){u,h[v],w};h[v]=cnt;

}

void qd(int u,int fa,int len){

	if(len>r)r=len,t=u;

	for(int i=h[u];i;i=e[i].next){

		int v=e[i].to;

		if(v^fa)qd(v,u,len+e[i].w);

	}

}

void dfs(int u,int fa){

    s[u].clear();f[u]=0;

    for(int i=h[u];i;i=e[i].next){

        int v=e[i].to;if(v==fa)continue;

        dfs(v,u);

        if(f[v]+e[i].w>=mid)tot++;

        else s[u].insert(f[v]+e[i].w);

    }

    if(!s[u].size())return;

    while(s[u].size()>1){

        it=s[u].begin();s[u].erase(it);

        ir=s[u].lower_bound(mid-(*it));

        if(ir==s[u].end()){f[u]=*it;continue;}

        s[u].erase(ir);tot++;

    }

    if(s[u].size()==1)f[u]=*(s[u].begin());

}

int main(){

    n=re(),m=re();

    for(int i=1,u,v,w;i<n;i++){

        u=re(),v=re(),w=re();

        link(u,v,w);

    }

	qd(1,0,0);qd(t,0,0);

    while(l<=r){

        tot=0;mid=(l+r)>>1;dfs(1,0);

        if(tot>=m)ans=mid,l=mid+1;

        else r=mid-1;

    }

    printf("%d\n",ans);

    return 0;

}