【点分治】Race

分治, 树论

传送门：BZOJ2599

思路：点分治即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
#define N 300000
#define M 1200000
#define INF 0x3f3f3f3f
int n,m,x,y,z,rt,tot,ans,sz[N],mx[N],head[N],d[M];
bool vis[N];
struct edge{int v,nxt,l;}e[N*2];
int getint(){
    char ch; int sum=0,fh=1;
    for (ch=getchar();ch<'0' || ch>'9';ch=getchar()) fh=ch=='-'?-1:1;
    for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
    return sum*fh;
}
void add(int x,int y,int z){e[++tot].v=y; e[tot].nxt=head[x]; e[tot].l=z; head[x]=tot;}
void getroot(int u,int fa,int sum){
    sz[u]=1; mx[u]=0;
    for (int i=head[u],v;i;i=e[i].nxt)
        if (!vis[v=e[i].v] && v!=fa){
            getroot(v,u,sum);
            sz[u]+=sz[v];
            mx[u]=max(mx[u],sz[v]);
        }
    mx[u]=max(mx[u],sum-sz[u]);
    if (mx[u]<mx[rt]) rt=u;
}
void getans(int u,int fa,int dist,int tmp){
    if (dist>m) return;
    ans=min(ans,d[m-dist]+tmp);
    for (int i=head[u],v;i;i=e[i].nxt)
        if (!vis[v=e[i].v] && v!=fa) getans(v,u,dist+e[i].l,tmp+1);
}
void update(int u,int fa,int dist,int tmp){
    if (dist>m) return;
    d[dist]=min(d[dist],tmp);
    for (int i=head[u],v;i;i=e[i].nxt)
        if (!vis[v=e[i].v] && v!=fa) update(v,u,dist+e[i].l,tmp+1);
}
void empty(int u,int fa,int dist){
    if (dist>m) return;
    d[dist]=INF;
    for (int i=head[u],v;i;i=e[i].nxt)
        if (!vis[v=e[i].v] && v!=fa) empty(v,u,dist+e[i].l);
}
void calc(int u){
    d[0]=0;
    for (int i=head[u],v;i;i=e[i].nxt)
        if (!vis[v=e[i].v]){
            getans(v,0,e[i].l,1); update(v,0,e[i].l,1);
        }
    for (int i=head[u],v;i;i=e[i].nxt)
        if (!vis[v=e[i].v]) empty(v,0,e[i].l);
}
void solve(int u){
    vis[u]=1; calc(u);
    for (int i=head[u],v;i;i=e[i].nxt)
        if (!vis[v=e[i].v]){
            rt=0; getroot(v,0,sz[v]); solve(rt);
        }
}
int main(){
    n=getint(); m=getint();
    for (int i=1;i<n;i++){
        x=getint()+1; y=getint()+1; z=getint();
        add(x,y,z); add(y,x,z);
    }
    memset(d,0x3f,sizeof d); ans=mx[rt=0]=INF;
    getroot(1,0,n); solve(rt);
    printf("%d\n",ans==INF?-1:ans);
    return 0;
}