首页 > 代码库 > poj1741 Tree（点分治）

poj1741 Tree（点分治）

2024-09-07 10:37:45   215人阅读

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001). 
Define dist(u,v)=The min distance between node u and v. 
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k. 
Write a program that will count how many pairs which are valid for a given tree. 

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l. 
The last test case is followed by two zeros. 

Output

For each test case output the answer on a single line.

Sample Input

5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0

Sample Output

8


题目大意：

给定一棵N个结点的带权树。 定义dist(u，v)=u，v两点间的路径长度，路径的长度定义为路径上所有边的权和。 给定一个K，如果对于不同的两个结点a，b，如果满足dist(a，b)≤K，则称(a，b)为合法点对。 求合法点对个数。


这道题是点分治的模板题，具体可参考2009年漆子超的国家集训队论文《分治算法在树的路径问题中的应用》
第一次写点分治，非常不熟练，也犯了一些变量打错的sb错误。
AC代码：
  1 program rrr(input,output);
  2 type
  3   etype=record
  4      t,l,next:longint;
  5   end;
  6 var
  7   e:array[0..20020]of etype;
  8   a,q,father,siz,f,w:array[0..10010]of longint;
  9   v:array[0..10010]of boolean;
 10   n,m,i,min,x,y,l,cnt,r,h,t,ans:longint;
 11 procedure add(x,y,l:longint);
 12 begin
 13    inc(cnt);e[cnt].t:=y;e[cnt].l:=l;e[cnt].next:=a[x];a[x]:=cnt;
 14 end;
 15 function max(a,b:longint):longint;
 16 begin
 17    if a>b then exit(a) else exit(b);
 18 end;
 19 procedure sort(q,h:longint);
 20 var
 21   i,j,x,t:longint;
 22 begin
 23    i:=q;j:=h;x:=w[(i+j)>>1];
 24    repeat
 25      while w[i]<x do inc(i);
 26      while x<w[j] do dec(j);
 27      if i<=j then
 28         begin
 29            t:=w[i];w[i]:=w[j];w[j]:=t;
 30            inc(i);dec(j);
 31         end;
 32    until i>j;
 33    if j>q then sort(q,j);
 34    if i<h then sort(i,h);
 35 end;
 36 function sum(h,t:longint):longint;
 37 var
 38   i,j,ans:longint;
 39 begin
 40    sort(h,t);
 41    ans:=0;j:=t;
 42    for i:=h to t do
 43       begin
 44          while (w[i]+w[j]>m) and (j>i) do dec(j);
 45          if i=j then break;
 46          ans:=ans+j-i;
 47       end;
 48    exit(ans);
 49 end;
 50 procedure solve(k:longint);
 51 var
 52   i,j:longint;
 53 begin
 54    h:=0;t:=1;q[1]:=k;father[k]:=0;
 55    while h<t do
 56       begin
 57          inc(h);
 58          i:=a[q[h]];
 59          while i<>0 do
 60             begin
 61                if not v[e[i].t] and (e[i].t<>father[q[h]]) then
 62                   begin
 63                      father[e[i].t]:=q[h];
 64                      inc(t);q[t]:=e[i].t;
 65                   end;
 66                i:=e[i].next;
 67             end;
 68       end;
 69    if t=1 then exit;
 70    for i:=1 to t do begin siz[q[i]]:=1;f[q[i]]:=0; end;
 71    min:=n;
 72    for i:=t downto 2 do
 73       begin
 74          r:=max(f[q[i]],t-siz[q[i]]);
 75          if r<min then begin min:=r;j:=q[i]; end;
 76          inc(siz[father[q[i]]],siz[q[i]]);
 77          if siz[q[i]]>f[father[q[i]]] then f[father[q[i]]]:=siz[q[i]];
 78       end;
 79    if f[k]<min then j:=k;
 80    r:=a[j];cnt:=0;
 81    while r<>0 do
 82       begin
 83          if not v[e[r].t] then
 84             begin
 85                h:=0;t:=1;q[1]:=e[r].t;father[e[r].t]:=j;w[cnt+1]:=e[r].l;
 86                while h<t do
 87                   begin
 88                      inc(h);
 89                      i:=a[q[h]];
 90                      while i<>0 do
 91                         begin
 92                            if not v[e[i].t] and (e[i].t<>father[q[h]]) then
 93                               begin
 94                                  father[e[i].t]:=q[h];
 95                                  inc(t);q[t]:=e[i].t;w[cnt+t]:=w[cnt+h]+e[i].l;
 96                               end;
 97                            i:=e[i].next;
 98                         end;
 99                   end;
100                ans:=ans-sum(cnt+1,cnt+t);
101                cnt:=cnt+t;
102             end;
103          r:=e[r].next;
104       end;
105    inc(cnt);w[cnt]:=0;
106    ans:=ans+sum(1,cnt);
107    v[j]:=true;i:=a[j];
108    while i<>0 do begin if not v[e[i].t] then solve(e[i].t);i:=e[i].next; end;
109 end;
110 begin
111    assign(input,‘r.in‘);assign(output,‘r.out‘);reset(input);rewrite(output);
112    while true do
113       begin
114          read(n,m);if (n=0) and (m=0) then break;
115          for i:=1 to n do a[i]:=0;cnt:=0;
116          for i:=1 to n-1 do begin readln(x,y,l);add(x,y,l);add(y,x,l); end;
117          ans:=0;
118          for i:=1 to n do v[i]:=false;
119          solve(1);
120          writeln(ans);
121       end;
122    close(input);close(output);
123 end.


 


 
poj1741 Tree（点分治）






























        

            
                
                  
                
                

                    联系

                    我们