NOIP2018 Day1 T3 트랙 건설-2부 세트 2점-dp-욕심

장내 심로 역정: 우선 이것은 분명히 dp인 것 같다.침구라는 문제는 다항식으로 할 수 있습니까?잠시 생각하다가 부분분표를 열거했는데 m=1로 직경을 구하고 체인을 만들 줄 알고 별을 만들 줄 알았어요.응, 확정했어. 분명히 dp야. 꼭 2점 답이야.그리고 폭력을 쓰고 사슬을 쓰기 시작했을 때 갑자기 생각했어요. 에이, 별이 뭐였지???자세히 냉정해 보니 별의 생각에 문제가 있었다.당황하기 시작해서 체인을 반쯤 썼다.냉정하게 생각해보니 예전에 cf에서 풀었던 문제가 생각났다. 그때 문제를 잘못 읽었다. 틀린 문제를 읽는 토대에서 어떤 사람이 나에게 잘못된 방법을 알려주었다. 당시에는 dp의 2차원 상태가 욕심을 부릴 수 있지만 그 틀린 문제에 대해 잘못된 결론을 내렸다.2분의 1의 답안을 추측한 후에 유사하게 할 수 있다. 생각해 보니 반례가 없다.그리고 모르는 쓰레기 더미를 생각해 보니 지금 체인이 있다. 가능한 한 많은 두 개의 짝을 지어 짝짓기의 길이와 2점보다 큰 값을 만들어야 한다. 방법은 이미 2점보다 큰 값을 가진 체인이다. 체인을 막론하고 크든 작든 모두 가능한 한 작은 짝짓기를 선택한다.이렇게 하면 큰 사례와 촬영을 한 적이 없다. 작은 데이터를 찍었는데 이렇게 하면 마지막에 남겨진 것이 가장 크다는 것을 보장할 수 없다. 데이터 범위를 결합시켜 2점이 더 필요하다는 것을 깨닫고 큰 사례와 촬영을 통과했다.다 했어.

#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define gc getchar()
using namespace std;
inline int inn()
{
    int x,ch;while((ch=gc)<'0'||ch>'9');
    x=ch^'0';while((ch=gc)>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^'0');return x;
}
const int N=50010;
struct edges{
    int to,pre,wgt;
}e[N<<1];int h[N],etop,a[N],b[N],c[N];
inline int add_edge(int u,int v,int w)
{ return e[++etop].to=v,e[etop].pre=h[u],e[etop].wgt=w,h[u]=etop; }
namespace subtask_std{
    int sv[N],res[N],vis[N];
    inline int check(int cnt,int bp,int v)
    {
        rep(i,1,cnt) vis[i]=0;if(bp) vis[bp]=1;int mxans=0;
        for(int i=cnt,j=1;i;i--)
        {
            if(vis[i]) continue;while(j<i&&(vis[j]||sv[j]+sv[i]<v)) j++;
            if(j<i&&!vis[j]&&sv[j]+sv[i]>=v) vis[i]=vis[j]=1,mxans++,j++;
        }
        return mxans;
    }
    int dfs(int x,int fa,int v)
    {
        int cnt=0,ans=0;
        for(int i=h[x],y;i;i=e[i].pre)
            if((y=e[i].to)^fa) ans+=dfs(y,x,v);
        for(int i=h[x],y;i;i=e[i].pre)
            if((y=e[i].to)^fa) sv[++cnt]=res[y]+e[i].wgt;
        res[x]=0;if(!cnt) return ans;
        sort(sv+1,sv+cnt+1);
        while(cnt&&sv[cnt]>=v) ans++,cnt--;
        int mxans=check(cnt,0,v),L=1,R=cnt,mid=(L+R)>>1;
        while(L<=R)
        {
            if(check(cnt,mid,v)==mxans) L=mid+1;
            else R=mid-1;mid=(L+R)>>1;
        }
        return res[x]=sv[R],ans+=mxans;
    }
    inline int acceptable_solution(int n,int m)
    {
        memset(h,0,sizeof(int)*(n+1)),etop=0;
        rep(i,1,n-1) add_edge(a[i],b[i],c[i]),add_edge(b[i],a[i],c[i]);
        int L=1,R=0;rep(i,1,n-1) R+=c[i];
        for(int mid=(L+R)>>1;L<=R;mid=(L+R)>>1)
            if(dfs(1,0,mid)>=m) L=mid+1;
            else R=mid-1;
        return !printf("%d
",R);
    }
}
int main()
{
    int n=inn(),m=inn();
    rep(i,1,n-1) a[i]=inn(),b[i]=inn(),c[i]=inn();
    return subtask_std::acceptable_solution(n,m);
}