BZOJ

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.