POJ 1741

POJ传送门
BZOJ不稳定的传送门

对于每次找到的根,算出来所有到根长度不超过$K$的路径,看两两组合能构成多少条经过根的长度不超过$K$的路径,更新答案

但这样的路径可能会重复经过同一个点,所以再减掉子树中重复算的


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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
program poj_1741;
var l:array[1..20000]of record ed,pre,len:longint; end;
lst,size,d,seq:array[1..10000]of longint;
n,lim,i,a,b,tot,len,maxsize,root,ans:longint;
v:array[1..10000]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 dfs(t,fa:longint);
var k,max:longint;
begin
size[t]:=1;
max:=0;
k:=lst[t];
while k<>0 do
begin
if (l[k].ed<>fa)and(not v[l[k].ed]) then
begin
dfs(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<maxsize then
begin
maxsize:=max;
root:=t;
end;
end;
procedure qsort(l,r:longint);
var i,j,mid,p:longint;
begin
i:=l;
j:=r;
mid:=d[seq[(l+r)>>1]];
repeat
while d[seq[i]]<mid do inc(i);
while d[seq[j]]>mid do dec(j);
if i<=j then
begin
p:=seq[i];
seq[i]:=seq[j];
seq[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure calc_dis(t,fa:longint);
var k:longint;
begin
inc(len);
seq[len]:=t;
k:=lst[t];
while k<>0 do
begin
if (not v[l[k].ed])and(l[k].ed<>fa)and(d[t]+l[k].len<=lim) then
begin
d[l[k].ed]:=d[t]+l[k].len;
calc_dis(l[k].ed,t);
end;
k:=l[k].pre;
end;
end;
function calc(t,dis:longint):longint;
var l,r:longint;
begin
d[t]:=dis;
len:=0;
calc_dis(t,0);
qsort(1,len);
calc:=0;
r:=len;
for l:=1 to len-1 do
begin
if d[seq[l]]+d[seq[l+1]]>lim then break;
while (r>l)and(d[seq[l]]+d[seq[r]]>lim) do dec(r);
while (r<len)and(d[seq[l]]+d[seq[r+1]]<=lim) do inc(r);
inc(calc,r-l);
end;
end;
procedure solve(t:longint);
var k,p:longint;
begin
p:=tot;
v[t]:=true;
inc(ans,calc(t,0));
k:=lst[t];
while k<>0 do
begin
if not v[l[k].ed] then
begin
dec(ans,calc(l[k].ed,l[k].len));
if size[l[k].ed]<size[t] then tot:=size[l[k].ed] else tot:=p-size[t];
maxsize:=maxlongint;
dfs(l[k].ed,t);
solve(root);
end;
k:=l[k].pre;
end;
end;
begin
repeat
readln(n,lim);
if (n=0)and(lim=0) then exit;
for i:=1 to n do lst[i]:=0;
fillchar(v,sizeof(v),false);
tot:=0;
for i:=1 to n-1 do
begin
readln(a,b,len);
link(a,b,len);
link(b,a,len);
end;
tot:=n;
maxsize:=maxlongint;
ans:=0;
dfs(1,0);
solve(root);
writeln(ans);
until false;
end.