【树上的分治】poj1741

树是一种优美的数据结构（嗯嗯，这句话看过百遍了）。

 

这道题目的描述很清晰，给你一颗N个点（N<10000）有边权的无根树，要你统计满足距离不超过k的点对个数；

 

因为有多组数据的存在，所以平方的算法是不行的，便向NlogN靠近（貌似用什么NB数据结构可以O(N)？天啊。。）。

仔细分析了一下，其实是看了论文，对于每个满足条件的点对，他们之间有一条路径，对于每一个点，要么在这个路径上，要么在路径之外，这就让我们想到了使用分治算法：

      对于每一颗树，我们找到最优的这样一个根，使得以他儿子为根的子树中大小最大的最小。这样选跟是有意义的，可以使得递归分下去的层数最少，这样很容易证明分出的层数是小于等于logN层的（最坏情况一条链）。

      我们找到这样的根了，然后只要统计经过他的路径的条数就可以了，条件就是dep(i)+dep(j)<=k (i和j属于不同的子树)—> dep(i)<=k-dep(j),我是利用treap统计的，好像可以O(N)的线性扫描，无解。

      自己做完后，在递归到每颗子树就可以了。因为一共有logN层，每层要NlogN的统计，所以复杂度是 N log²N 的，速度很快，300ms。

 

代码自我感觉良好：

 

program poj1741; var d,son,l,r,v,w,next,p,c,s,go:array[0..30000] of longint; o:array[0..20000] of boolean; n,len,best,i,min,t,tot,tmp,ans,root,a,b,cc:longint; procedure left(var i:longint); begin tmp:=r[i];r[i]:=l[tmp];l[tmp]:=i; s[i]:=s[l[i]]+s[r[i]]+1; s[tmp]:=s[l[tmp]]+s[r[tmp]]+1; i:=tmp; end; procedure right(var i:longint); begin tmp:=l[i];l[i]:=r[tmp];r[tmp]:=i; s[i]:=s[l[i]]+s[r[i]]+1; s[tmp]:=s[l[tmp]]+s[r[tmp]]+1; i:=tmp; end; procedure insert(var i:longint;k:longint); begin if i=0 then begin inc(t);i:=t; s[i]:=1; w[i]:=k; v[i]:=random(maxlongint); l[i]:=0;r[i]:=0; end else if w[i]>k then begin insert(l[i],k);inc(s[i]); if v[l[i]]>v[i] then right(i); end else begin insert(r[i],k);inc(s[i]); if v[r[i]]>v[i] then left(i); end; end; function rank(i,k:longint):longint; begin if i=0 then exit(0); if w[i]<=k then rank:=s[l[i]]+1+rank(r[i],k) else rank:=rank(l[i],k); end; procedure link(a,b,cc:longint); begin inc(t); next[t]:=d[a];d[a]:=t;p[t]:=b;c[t]:=cc; end; procedure dfs1(fa,i,dep:longint); var k,j:longint; begin inc(ans,rank(root,len-dep)); k:=d[i];j:=p[k]; son[i]:=1; while k<>0 do begin if (j<>fa)and(not o[j]) then begin dfs1(i,j,dep+c[k]); inc(son[i],son[j]); end; k:=next[k];j:=p[k]; end; end; procedure dfs2(fa,i,dep:longint); var k,j,ms:longint; begin insert(root,dep); ms:=tot-son[i]; k:=d[i];j:=p[k]; while k<>0 do begin if (j<>fa)and(not o[j]) then begin dfs2(i,j,dep+c[k]); if son[j]>ms then ms:=son[j]; end; k:=next[k];j:=p[k]; end; if ms<min then begin min:=ms;best:=i; end; end; procedure deal(i:longint); var k,j:longint; begin o[i]:=true; root:=0;t:=0; insert(root,0); k:=d[i];j:=p[k]; while k<>0 do begin if not o[j] then begin min:=maxlongint; dfs1(i,j,c[k]);tot:=son[j]; dfs2(i,j,c[k]);go[j]:=best; end; k:=next[k];j:=p[k]; end; k:=d[i];j:=p[k]; while k<>0 do begin if not o[j] then deal(go[j]); k:=next[k];j:=p[k]; end; end; begin readln(n,len); randomize; while n<>0 do begin t:=0;ans:=0; fillchar(o,sizeof(o),false); fillchar(d,sizeof(d),0); for i:=1 to n-1 do begin readln(a,b,cc); link(a,b,cc);link(b,a,cc); end; deal(1); writeln(ans); readln(n,len); end; end.