洛谷 4149 [IOI2011]Race——点分治

题目：https://www.luogu.org/problemnew/show/P4149

第一道点分治！

点分治大约是每次找重心，以重心为根做一遍树形dp；然后对于该根的每个孩子，递归下去。递归之前把该根的vis设成1,就相当于删掉该点这边的这部分。

对于这道题，要开一个1e6的桶，就不能给每个节点都开了；所以弄一个全局的，在递归给孩子之前都赋成初值就行了。

注意要弄完一个孩子再把它的点的值加到该根的数组里，作为“之前孩子的值”；而且递归之前赋初值memset也比较慢，开一个栈之类的就都好了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=2e5+,M=1e6+,INF=0x3f3f3f3f;

int n,K,f[M],hd[N],xnt,to[N<<],w[N<<],nxt[N<<],sta[N][],top;

int siz[N],mn,dis[N],sl[N],ans=N;

bool vis[N];

void add(int x,int y,int z)

{

    to[++xnt]=y;nxt[xnt]=hd[x];w[xnt]=z;hd[x]=xnt;

    to[++xnt]=x;nxt[xnt]=hd[y];w[xnt]=z;hd[y]=xnt;

}

void getrt(int cr,int fa,int &rt,int s)

{

    siz[cr]=;int mx=;

    for(int i=hd[cr],v;i;i=nxt[i]) if(!vis[v=to[i]]&&v!=fa)

    {

        getrt(v,cr,rt,s);siz[cr]+=siz[v];mx=max(mx,siz[v]);

    }

    mx=max(mx,s-siz[cr]);

    if(mx<mn)mn=mx,rt=cr;

}

void dfs(int cr,int fa)

{

    siz[cr]=;

    for(int i=hd[cr],v;i;i=nxt[i]) if(!vis[v=to[i]]&&v!=fa)

    {

        dis[v]=dis[cr]+w[i];sl[v]=sl[cr]+;

        if(K>=dis[v])

        {

            ans=min(ans,sl[v]+f[K-dis[v]]);

            sta[++top][]=dis[v];sta[top][]=sl[v];

        }

        dfs(v,cr);siz[cr]+=siz[v];

    }

}

void solve(int cr)

{

    vis[cr]=;int p0=;

    for(int i=hd[cr],v;i;i=nxt[i]) if(!vis[v=to[i]])

    {

        dis[v]=w[i];sl[v]=;

        if(K>=dis[v])

        {

            ans=min(ans,sl[v]+f[K-dis[v]]);

            sta[++top][]=dis[v];sta[top][]=sl[v];

        }

        dfs(v,);

        for(int i=p0;i<=top;i++)f[sta[i][]]=min(f[sta[i][]],sta[i][]);

        p0=top+;

    }

    for(int i=;i<=top;i++)f[sta[i][]]=INF;top=;

    for(int i=hd[cr],v;i;i=nxt[i]) if(!vis[v=to[i]])

    {

        mn=N;int rt;getrt(v,,rt,siz[v]);

        solve(rt);

    }

}

int main()

{

    scanf("%d%d",&n,&K);int x,y,z;

    for(int i=;i<n;i++)

    {

        scanf("%d%d%d",&x,&y,&z);x++;y++;add(x,y,z);

    }

    memset(f,0x3f,sizeof f);f[]=;

    mn=N;int rt;getrt(,,rt,n);solve(rt);

    printf("%d\n",ans==N?-:ans);

    return ;

}