POJ

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.