【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<<1];

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] = 1;
    weight[u] = 0;
    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] + 1;
            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] = 0;
    visited[u] = true;
    num[0] = 0;
    for (i = head[u]; i; i = e[i].nxt)
    {
        v = e[i].to;
        w = e[i].w;
        if (!visited[v])
        {
            dep[v] = 1;
            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 = 0;
            getroot(v,0,size[v]);
            work(root);
        }
    }    
}

int main()
{
    
    scanf("%lld%lld",&n,&k);
    for (i = 1; i <= k; i++) num[i] = INF;
    for (i = 1; i < n; i++)
    {
        scanf("%lld%lld%lld",&u,&v,&w);
        u++; v++;
        addedge(u,v,w);
        addedge(v,u,w);
    }
    root = 0;
    size[0] = weight[0] = n;
    getroot(1,0,n);
    ans = INF;
    work(root);
    if (ans < n) printf("%lld
",ans);
    else printf("-1
");
    return 0;

}