poj1741 bzoj2152

树分治入门

poj1741是男人八题之一，经典的树分治的题目
这里用到的是点分治
核心思想是我们把某个点i作为根，把路径分为过点i和不过点i
先统计过点i这样的路径数，然后在统计其子树中的答案，这样就不断地划分成规模较小子问题。
要使划分最优，我们每次都选的是树的重心

  1 type node=record
  2        len,next,po:longint;
  3      end;
  4 
  5 var e:array[0..80010] of node;
  6     w,p,d,a,size:array[0..40010] of longint;
  7     v:array[0..40010] of boolean;
  8     root,sum,n,t,ans,k,i,x,y,z,len:longint;
  9 
 10 function max(a,b:longint):longint;
 11   begin
 12     if a>b then exit(a) else exit(b);
 13   end;
 14 
 15 procedure sort(l,r: longint);
 16   var i,j,x,y: longint;
 17   begin
 18     i:=l;
 19     j:=r;
 20     x:=a[(l+r) div 2];
 21     repeat
 22       while a[i]<x do inc(i);
 23       while x<a[j] do dec(j);
 24       if not(i>j) then
 25       begin
 26         y:=a[i];
 27         a[i]:=a[j];
 28         a[j]:=y;
 29         inc(i);
 30         j:=j-1;
 31       end;
 32     until i>j;
 33     if l<j then sort(l,j);
 34     if i<r then sort(i,r);
 35   end;
 36 
 37 procedure add(x,y,z:longint);
 38   begin
 39     inc(len);
 40     e[len].po:=y;
 41     e[len].len:=z;
 42     e[len].next:=p[x];
 43     p[x]:=len;
 44   end;
 45 
 46 procedure getroot(x,fa:longint);  //选择重心
 47   var i,y:longint;
 48   begin
 49     i:=p[x];
 50     size[x]:=1;
 51     w[x]:=0;
 52     while i<>0 do
 53     begin
 54       y:=e[i].po;
 55       if (not v[y]) and (y<>fa) then
 56       begin
 57         getroot(y,x);
 58         size[x]:=size[x]+size[y];
 59         w[x]:=max(w[x],size[y]);
 60       end;
 61       i:=e[i].next;
 62     end;
 63     w[x]:=max(w[x],sum-size[x]);
 64     if w[x]<w[root] then root:=x;
 65   end;
 66 
 67 procedure deep(x,fa:longint);
 68   var i,y:longint;
 69   begin
 70     inc(t);
 71     a[t]:=d[x];
 72     i:=p[x];
 73     while i<>0 do
 74     begin
 75       y:=e[i].po;
 76       if not v[y] and (y<>fa) then
 77       begin
 78         d[y]:=d[x]+e[i].len;
 79         deep(y,x);
 80       end;
 81       i:=e[i].next;
 82     end;
 83   end;
 84 
 85 function calc(x,now:longint):longint;
 86   var i,l,r:longint;
 87   begin
 88     t:=0;
 89     d[x]:=now;
 90     calc:=0;
 91     deep(x,0);
 92     sort(1,t);
 93     l:=1;
 94     r:=t;
 95     while l<r do
 96     begin
 97       if a[l]+a[r]<=k then
 98       begin
 99         calc:=calc+r-l;
100         inc(l);
101       end
102       else dec(r);
103     end;
104   end;
105 
106 procedure work(x:longint);
107   var i,y:longint;
108   begin
109     ans:=ans+calc(x,0);  
110     i:=p[x];
111     v[x]:=true;
112     while i<>0 do
113     begin
114       y:=e[i].po;
115       if not v[y] then
116       begin
117         ans:=ans-calc(y,e[i].len);  //之前的计算会导致lca不为root的点对被算入，实际它们的路径不过重心，这里要减去
118         sum:=size[y];
119         root:=0;
120         getroot(y,0);
121         work(root);
122       end;
123       i:=e[i].next;
124     end;
125   end;
126 
127 begin
128   readln(n,k);
129   while n<>0 do
130   begin
131     len:=0;
132     fillchar(p,sizeof(p),0);
133     for i:=1 to n-1 do
134     begin
135       readln(x,y,z);
136       add(x,y,z);
137       add(y,x,z);
138     end;
139     fillchar(v,sizeof(v),false);
140     sum:=n;
141     w[0]:=2147483647;
142     getroot(1,0);
143     ans:=0;
144     work(root);
145     writeln(ans);
146     readln(n,k);
147   end;
148 end.
149 
150

View Code

bzoj2152是更水的树分治……