[IOI2011] Race

题目描述

给一棵树，每条边有权。求一条简单路径，权值和等于 \(k\)，且边的数量最小。

输入格式

第一行包含两个整数 \(n,k\)，表示树的大小与要求找到的路径的边权和。

接下来 \(n-1\) 行，每行三个整数 \(u_i,v_i,w_i\)，代表有一条连接 \(u_i\) 与 \(v_i\)，边权为 \(w_i\) 的无向边。

注意：点从 \(0\) 开始编号。

输出格式

输出一个整数，表示最小边数量。

如果不存在这样的路径，输出 \(-1\)。

样例 #1

样例输入 #1

4 3
0 1 1
1 2 2
1 3 4

样例输出 #1

2

提示

对于 \(100\%\) 的数据，保证 \(1\leq n\leq 2\times10^5\)，\(0\leq k,w_i\leq 10^6\)，\(0\leq u_i,v_i<n\)。

solution

对于每个分治点x,遍历到的每个儿子y,将所有在y之前的儿子加入一个桶中，桶的下标存距离，桶的值存dep,而路径(u,v)经过的边数就是dep[u]+dep[v]-2*dep[x]（这里dep[x]设为0了，所以代码里没有）

但是dis的分布可能很离散，所以还要用一个数组A来记录当前桶内出现过的dis,便于删桶

然后这题就愉快的做完了

Code:

#include<bits/stdc++.h>
const int N=2e5+5;
const int inf=1e6+5;
using namespace std;
struct Node{
    int x,y;
};
int n,k,e_cnt,tot,cent,ans,ddd;
int nxt[N<<1],to[N<<1],w[N<<1],head[N],vis[N];
int dis[N],siz[N],mx[N],dep[N];
void add(int x,int y,int z)
{

    to[++e_cnt]=y;nxt[e_cnt]=head[x];w[e_cnt]=z;
    head[x]=e_cnt;
}
void get_cent(int u,int fa)
{
    siz[u]=1;
    mx[u]=0;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(fa==v||vis[v])continue;
        get_cent(v,u);
        siz[u]+=siz[v];
        mx[u] = (siz[v] > mx[u] ? siz[v] : mx[u]);
    }
    mx[u] = (mx[u] > tot-siz[u] ? mx[u] : tot-siz[u]);
    cent = (mx[cent] <mx[u] ? cent : u);
}
int ba[inf],A[N];
inline int Min(int x,int y)
{
    return (x<y ? x : y);
}
vector<Node>Q;
void get_dis(int u,int fa)
{
    Q.push_back(Node{dis[u],dep[u]});
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(vis[v]||v==fa)continue;
        dis[v]=dis[u]+w[i];
        dep[v]=dep[u]+1;
        get_dis(v,u);
    }
}
void INIT()
{
    ans=inf;
    for(int i=0;i<=k;i++)ba[i]=inf;
}
void calc(int x)
{
    dis[x]=0;
    dep[x]=0;
    ba[0]=0;
    A[++A[0]]=0;
    for(int i=head[x];i;i=nxt[i])
    {
        int v=to[i];
        if(vis[v])continue;
        dep[v]=1;dis[v]=w[i];
        get_dis(v,x);
        for(auto To : Q)
        {
            int tmp = k - To.x;
            if(0<=tmp&&tmp<=k)
            ans=Min(ans,ba[tmp]+To.y);
        }
        for(auto To : Q)
        {
            if(To.x>k)continue;
            if(ba[To.x]==inf)A[++A[0]]=To.x;
            ba[To.x]=Min(ba[To.x],To.y);
        }
        Q.clear();
    }
    for(int i=0;i<=A[0];i++)
    {
        ba[A[i]]=inf;
    }
    A[0]=0;
}
void solve(int x)
{
    calc(x);
    vis[x]=1;
    for(int i=head[x],y;i;i=nxt[i])
    {
        y=to[i];
        if(vis[y])continue;
        mx[cent=0]=inf;tot=siz[y];
        get_cent(y,x);
        solve(cent);
    }
}
void work()
{
    cin>>n>>k;
    INIT();
    for(int i=1,x,y,z;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        x++,y++;
        add(x,y,z);
        add(y,x,z);
    }
    mx[cent=0]=inf;tot=n;
    get_cent(1,0);
    solve(cent);
    ans = (ans==inf ? -1 : ans);
    printf("%d",ans);
}
int main()
{
    //freopen("P4149_1.in","r",stdin);
    //("Race.out","w",stdout);
    work();
    return 0;
}