BZOJ 2599

不稳定的传送门

对于当前的重心,遍历当前重心的子树时,假设遍历到的点距重心距离为$d$,那么需要找在遍历过的当前重心的其他子树中是否走过一条长度为$k-d$的边,若存在一条长度为$k-d$的边,说明能拼成一条长度为$k$的路径,更新答案,为了更新答案还要记录一下到达每个长度所需的最小边数

具体实现需要开一个数组存一个类似时间标记的东西,比如遍历到距离为$d$的点时,就把数组中下标为$d$的值赋为当前$root$,表示在$root$的子树中遍历到过一条长度为$d$的边,搜其他子树再遇到时直接判断下标$k-d$的地方存的$root$是否等于当前$root$就行了,若等于就可以合法地拼在一起

若$root$的子树中出现过多条长度相同的路径,取经过边数最少的那个

每次搜完一棵子树后将这棵子树合并进当前状态中


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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
program bzoj_2599;
var l:array[1..400000]of record ed,pre,len:longint; end;
lst,size,d,e:array[1..200000]of longint;
s:array[0..1000000]of record rt,e:longint; end;
n,len,i,tot,a,b,c,min,root,ans:longint;
v:array[1..200000]of boolean;
procedure link(a,b,len:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
l[tot].len:=len;
end;
procedure getroot(t,fa:longint);
var k,max:longint;
begin
size[t]:=1;
k:=lst[t];
max:=0;
while k<>0 do
begin
if (l[k].ed<>fa)and(not v[l[k].ed]) then
begin
getroot(l[k].ed,t);
if size[l[k].ed]>max then max:=size[l[k].ed];
inc(size[t],size[l[k].ed]);
end;
k:=l[k].pre;
end;
if tot-size[t]>max then max:=tot-size[t];
if max<min then
begin
min:=max;
root:=t;
end;
end;
procedure find(t,fa:longint);
var k:longint;
begin
if d[t]>len then exit;
if (s[len-d[t]].rt=root)and(e[t]+s[len-d[t]].e<ans) then ans:=e[t]+s[len-d[t]].e;
k:=lst[t];
while k<>0 do
begin
if (l[k].ed<>fa)and(not v[l[k].ed]) then
begin
d[l[k].ed]:=d[t]+l[k].len;
e[l[k].ed]:=e[t]+1;
find(l[k].ed,t);
end;
k:=l[k].pre;
end;
end;
procedure merge(t,fa:longint);
var k:longint;
begin
if d[t]>len then exit;
if s[d[t]].rt<>root then
begin
s[d[t]].rt:=root;
s[d[t]].e:=e[t];
end else if e[t]<s[d[t]].e then s[d[t]].e:=e[t];
k:=lst[t];
while k<>0 do
begin
if (l[k].ed<>fa)and(not v[l[k].ed]) then merge(l[k].ed,t);
k:=l[k].pre;
end;
end;
procedure solve(t:longint);
var p,k:longint;
begin
p:=tot;
v[t]:=true;
s[0].rt:=t;
s[0].e:=0;
k:=lst[t];
while k<>0 do
begin
if not v[l[k].ed] then
begin
d[l[k].ed]:=l[k].len;
e[l[k].ed]:=1;
find(l[k].ed,t);
merge(l[k].ed,t);
end;
k:=l[k].pre;
end;
k:=lst[t];
while k<>0 do
begin
if not v[l[k].ed] then
begin
if size[l[k].ed]<size[t] then tot:=size[l[k].ed] else tot:=p-size[t];
min:=maxlongint;
getroot(l[k].ed,t);
solve(root);
end;
k:=l[k].pre;
end;
end;
begin
readln(n,len);
tot:=0;
for i:=1 to n-1 do
begin
readln(a,b,c);
link(a+1,b+1,c);
link(b+1,a+1,c);
end;
tot:=n;
min:=maxlongint;
getroot(1,0);
ans:=maxlongint;
solve(root);
if ans<>maxlongint then writeln(ans) else writeln('-1');
end.