它这道题的分类是分治，但我还是觉得和树的关系更密切些。
也算是完成了第一个最简单的部分——基 本 算 法（更强大的在后面）。
是近来打过的比较难的题目了，因为涉及到很多新的东西
也花了挺长时间去学点分治和树的重心之类的东西。
首先，O(n^2)的爆搜还是很容易想到的吧，可惜过不了。
考虑无根树转有根树然后点分治。
首先把它转成有根树，那么所有的点对就被分成两类：经过根的和不经过根的，我们可以讨论一下
1.经过根的点对：只需要DFS得出它们距离根的距离dis[x],dis[y]，判断它们的和是否小于k
2.不经过根的点对：那么就分治下去，计算经过根的子树的根的点对（也分两种情况考虑）
最后需要注意的是有些点在经过根时被计算了一次，在子树中又被重复计算了多次，需要减去
在计算点对多少时，可以先排序，再用 two points 扫一次即可
如果根节点随意挑选那么很容易退化成链，所以每次找根节点都要找树（或子树）的重心。
然后就是一些细节问题了，具体看代码
CODE
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=10005; struct edge { int to,next,v; }e[N*2]; int head[N],t,n,m,i,x,y,z,k,size[N],f[N],dis[N],ans,sum,tot,root; bool vis[N]; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void write(int x) { if (x/10) write(x/10); putchar(x%10+'0'); } inline void add(int x,int y,int z) { e[++k].to=y; e[k].v=z; e[k].next=head[x]; head[x]=k; } inline int max(int a,int b) { return a>b?a:b; } inline void getroot(int now,int fa) { size[now]=1; f[now]=0; for (int i=head[now];i!=-1;i=e[i].next) if (e[i].to!=fa&&!vis[e[i].to]) { getroot(e[i].to,now); size[now]+=size[e[i].to]; f[now]=max(f[now],size[e[i].to]); } f[now]=max(f[now],sum-size[now]); if (f[now]<f[root]) root=now; } inline void DFS(int now,int fa,int d) { dis[++tot]=d; for (int i=head[now];i!=-1;i=e[i].next) if (e[i].to!=fa&&!vis[e[i].to]) DFS(e[i].to,now,d+e[i].v); } inline int work(int now,int d) { tot=0; DFS(now,-1,d); sort(dis+1,dis+tot+1); int l=1,r=tot,res=0; while (l<r) { while (dis[l]+dis[r]>m&&l<r) --r; res+=r-l++; } return res; } inline void solve(int now) { root=0; f[0]=1e9; getroot(now,-1); vis[root]=1; ans+=work(root,0); for (int i=head[root];i!=-1;i=e[i].next) if (!vis[e[i].to]) { ans-=work(e[i].to,e[i].v); sum=size[e[i].to]; solve(e[i].to); } } int main() { for (;;) { k=ans=0; memset(head,-1,sizeof(head)); memset(e,-1,sizeof(e)); memset(vis,0,sizeof(vis)); read(n); read(m); sum=n; if (n==0&&m==0) break; for (i=1;i<n;++i) { read(x); read(y); read(z); add(x,y,z); add(y,x,z); } solve(1); write(ans); putchar(' '); } return 0; }