【IOI 2011】Race

【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=2599

【算法】

点分治

【代码】

#include<bits/stdc++.h>

using namespace std;

#define MAXN 200010

#define MAXK 1000010

typedef long long ll;

const ll INF = 2e9;

ll i,n,k,u,v,w,tot,root,len,ans;

ll head[MAXN],size[MAXN],weight[MAXN],sum[MAXN],dep[MAXN],num[MAXK];

bool visited[MAXN];

struct Edge

{

    ll to,w,nxt;

} e[MAXN<<];

inline void addedge(ll u,ll v,ll w)

{

    tot++;

    e[tot] = (Edge){v,w,head[u]};

    head[u] = tot;

}

inline void getroot(ll u,ll fa,ll total)

{

    ll i,v;

    size[u] = ;

    weight[u] = ;

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        if (fa != v && !visited[v])

        {

            getroot(v,u,total);

            size[u] += size[v];

            weight[u] = max(weight[u],size[v]);

        }

    }

    weight[u] = max(weight[u],total - size[u]);

    if (weight[u] < weight[root]) root = u;

}

inline void dfs(ll u,ll fa)

{

    ll i,v,w;

    if (sum[u] <= k) ans = min(ans,dep[u]+num[k-sum[u]]);

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        w = e[i].w;

        if (fa != v && !visited[v])

        {

            dep[v] = dep[u] + ;

            sum[v] = sum[u] + w;

            dfs(v,u);

        }

    }

}

inline void update(ll u,ll fa)

{

    ll i,v;

    if (sum[u] <= k) num[sum[u]] = min(num[sum[u]],dep[u]);

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        if (fa != v && !visited[v]) update(v,u);

    }

}

inline void clear(ll u,ll fa)

{

    ll i,v;

    if (sum[u] <= k) num[sum[u]] = INF;

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        if (fa != v && !visited[v])

            clear(v,u);

    }

}

inline void work(ll u)

{

    ll i,v,w;

    dep[u] = ;

    visited[u] = true;

    num[] = ;

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        w = e[i].w;

        if (!visited[v])

        {

            dep[v] = ;

            sum[v] = w;

            dfs(v,u);

            update(v,u);

        }

    }

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        if (!visited[v]) clear(v,u);

    }

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        if (!visited[v])

        {

            root = ;

            getroot(v,,size[v]);

            work(root);

        }

    }

}

int main()

{

    scanf("%lld%lld",&n,&k);

    for (i = ; i <= k; i++) num[i] = INF;

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

    {

        scanf("%lld%lld%lld",&u,&v,&w);

        u++; v++;

        addedge(u,v,w);

        addedge(v,u,w);

    }

    root = ;

    size[] = weight[] = n;

    getroot(,,n);

    ans = INF;

    work(root);

    if (ans < n) printf("%lld\n",ans);

    else printf("-1\n");

    return ;

}