【点分治】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;
}