洛谷$P4149\ [IOI2011]\ Race$ 点分治

正解:点分治

解题报告:

传送门$QwQ$

昂先不考虑关于那个长度的限制考虑怎么做?

就开个桶,记录所有边的取值,每次加入边的时候查下是否可行就成$QwQ$

然后现在考虑加入这个长度的限制?就考虑把这个桶,本来是个$bool$数组记录可行嘛,现在就改成$int$数组记录最小长度

然后就做完辣,,,?$QwQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define int long long

#define gc getchar()

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=+,M=+,inf=1e9;

int n,K,head[N],ed_cnt,mxsz[N],sum,sz[N],rt,as,cnt,dis1[N],dis2[N],stp[M];

bool vis[N];

struct ed{int to,nxt,wei;}edge[N<<];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(ri x,ri y,ri z){edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;}

void dfs(ri x,ri fa)

{

    sz[x]=;mxsz[x]=;

    e(i,x)if(t(i)^fa && !vis[t(i)])dfs(t(i),x),sz[x]+=sz[t(i)],mxsz[x]=max(mxsz[x],sz[t(i)]);

    mxsz[x]=max(mxsz[x],sum-sz[x]);if(mxsz[x]<mxsz[rt])rt=x;

}

void dfs2(ri x,ri fa,ri d1,ri d2)

{if(d1>K)return;dis1[++cnt]=d1,dis2[cnt]=d2;e(i,x)if(!vis[t(i)] && t(i)^fa)dfs2(t(i),x,d1+w(i),d2+);}

il void cal(ri x)

{

    stp[]=;cnt=;

    e(i,x)

    {

        if(!vis[t(i)])

        {

            ri tmp=cnt;dfs2(t(i),x,w(i),);

            rp(j,tmp+,cnt){as=min(as,dis2[j]+stp[K-dis1[j]]);/*printf("x=%d to=%d dis1j=%d dis2j=%d stp=%d len=%d\n",x,t(i),dis1[j],dis2[j],stp[K-dis1[j]],K-dis1[j]);*/}

            rp(j,tmp+,cnt)stp[dis1[j]]=min(stp[dis1[j]],dis2[j]);

        }

    }

    //printf("  x=%d as=%d\n",x,as);

    rp(i,,cnt)stp[dis1[i]]=stp[K+];

}

void solv(ri x){/*printf("rt=%d\n",x);*/vis[x]=;cal(x);e(i,x)if(!vis[t(i)])sum=sz[x],rt=,dfs(t(i),x),solv(rt);}

signed main()

{

    //freopen("4149.in","r",stdin);freopen("4149.out","w",stdout);

    n=read();K=read();rp(i,,n-){ri x=read()+,y=read()+,z=read();ad(x,y,z);ad(y,x,z);}

    mxsz[rt]=sum=n;dfs(,);memset(stp,,sizeof(stp));as=stp[];solv(rt);printf("%lld\n",as==stp[K+]?-:as);

    return ;

}