BZOJ_2599_[IOI2011]Race

BZOJ_2599_[IOI2011]Race_点分治

Description

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

Input

第一行两个整数 n, k
第二..n行每行三个整数表示一条无向边的两端和权值 (注意点的编号从0开始)

Output

一个整数表示最小边数量如果不存在这样的路径输出-1

Sample Input

4 3
0 1 1
1 2 2
1 3 4

Sample Output

点分治。开个桶记录一下长度为x的路径最小的深度。

如何去重？我们开一个辅助桶存一下根的当前儿子的子树内的贡献。

保证每次查的时候用的是其他儿子的子树的路径。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 200050
#define inf 100000000
int head[N],to[N<<1],nxt[N<<1],cnt,val[N<<1];
int root,sum,siz[N],f[N],g[1000050],d[N],n,k,ans,dep[N],tmp[1000050],a[N],b[N];
bool used[N];
inline void add(int u,int v,int w) {
    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
void get_root(int x,int y) {
    siz[x]=1; f[x]=0;
    int i;
    for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]) {
        get_root(to[i],x);
        siz[x]+=siz[to[i]];
        f[x]=max(f[x],siz[to[i]]);
    }
    f[x]=max(f[x],sum-siz[x]);
    if(f[x]<f[root]) root=x;
}
void get_dep(int x,int y) {
    b[++b[0]]=x;
    a[++a[0]]=x;
    siz[x]=1;
    dep[x]=dep[y]+1;
    //printf("x=%d dep[x]=%d
",x,dep[x]);
    if(d[x]<=k) {
        ans=min(ans,g[k-d[x]]+dep[x]-2);
        tmp[d[x]]=min(tmp[d[x]],dep[x]);
    }
    int i;
    for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]) {
        d[to[i]]=d[x]+val[i];
        get_dep(to[i],x);
        siz[x]+=siz[to[i]];
    }
}
void work(int x) {
    g[0]=1;
    used[x]=1;
    d[x]=0;
    int i,j;
    b[0]=0;
    siz[x]=1;
    dep[x]=1;
    for(i=head[x];i;i=nxt[i]) if(!used[to[i]]) {
        a[0]=0;
        d[to[i]]=val[i];
        get_dep(to[i],x);
        siz[x]+=siz[to[i]];
        for(j=1;j<=a[0];j++) if(d[a[j]]<=k) {
            g[d[a[j]]]=min(g[d[a[j]]],tmp[d[a[j]]]);
        }
        for(j=1;j<=a[0];j++) if(d[a[j]]<=k) tmp[d[a[j]]]=inf;
    }
    for(i=1;i<=b[0];i++) if(d[b[i]]<=k) {
        g[d[b[i]]]=tmp[d[b[i]]]=inf;
    }
    g[0]=tmp[0]=inf;
    for(i=head[x];i;i=nxt[i]) if(!used[to[i]]) {
        root=0;
        sum=siz[to[i]];
        get_root(to[i],0);
        work(root);
    }
}
int main() {
    scanf("%d%d",&n,&k);
    int i,x,y,z;
    for(i=0;i<=k;i++) g[i]=tmp[i]=inf;
    for(i=1;i<n;i++) {
        scanf("%d%d%d",&x,&y,&z);
        x++;y++;
        add(x,y,z);add(y,x,z);
    }
    sum=n;
    f[0]=inf;
    ans=1<<30;
    root=0;
    get_root(1,0);
    work(root);
    printf("%d
",ans>n?-1:ans);
}