点分治的模板题。
总结一下点分治：核心就是关于重心的寻找。
对于一棵无根树，我们随机选择一个点作为根来处理树上路径。
最坏情况下有n层接近O（n）的复杂度，这时显然不太好。
那么我们就寻找到一个点（重心），满足他的最大的子树最小。这样可以最小化最大的递归层。
经过证明（证明略），最大的子树的最小的值的递归层必定是logn级别的。这样复杂度就优化了很多。
然后我们以重心为根去处理树上的路径，然后我们一开始分解出了整棵子树的重心。
但是当我们去处理它的子树时，也要保证log级别的复杂度，所以在处理子树内部时，需要对应子树内部也进行重心的分解。
显然为了不影响整体的答案，我们要先处理出根和子树的路径关系，然后再去处理子树内部，这样可以保证在对子树分解后。
不影响答案。
回到这题，统计树上路径<=k的点对数。
那么，对于根rt，在他的子树中，显然只有两种情况的路径。
1：不经过它的。
2：经过它的。
对于经过它的，也就是根和子树的路径关系，我们可以处理出根到子树中所有点的路径。
然后对他们进行一个排序，然后寻找相加后满足条件的路径数即可。
对于不经过它的，显然就是他的子节点内部的情况了，那么就可以递归它的子树去分解重心继续求。
可以发现，对于根和子树的路径关系的处理，会有不合法的路径组合情况，
即如果当前重心为1，那么1->3+1->5的路径情况显然不合法，但是可以发现这样的边组合满足在同一个子节点内部。
那么我们减去这部分不合法的方案即可。注意把子节点到根的边权放入，不然长度就不一样了。可能就不够长了。
吐槽一下poj的编译器版本有点老..
// Author: levil #include<iostream> #include<stdio.h> #include<queue> #include<algorithm> #include<math.h> #include<stack> #include<map> #include<limits.h> #include<vector> #include<string.h> #include<string> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e4+5; const int M = 1e4; const LL Mod = 2008; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int n,k,ssize[N],vis[N],head[N],mx = INF,rt,sz = n,dis[N],tot = 0,cnt = 0; struct Node{int to,dis,next;}e[N<<1]; LL ans = 0; inline void add(int u,int v,LL dis) { e[++cnt].to = v,e[cnt].dis = dis,e[cnt].next = head[u],head[u] = cnt; } void findroot(int u,int fa)//找重心 { ssize[u] = 1; int son = 0; for(int i = head[u];i;i = e[i].next) { int v = e[i].to,dis = e[i].dis; if(v == fa || vis[v]) continue; findroot(v,u); ssize[u] += ssize[v]; son = max(son,ssize[v]); } son = max(son,sz-ssize[u]); if(son < mx) mx = son,rt = u; } void Dis_slove(int u,int fa,int z)//处理距离 { dis[++tot] = z; for(int i = head[u];i;i = e[i].next) { int v = e[i].to,d = e[i].dis; if(v == fa || vis[v]) continue; Dis_slove(v,u,z+d); } } LL slove(int u,int val)//统计u和子树中的点的方案数 { tot = 0; Dis_slove(u,0,val); printf(" "); sort(dis+1,dis+tot+1); int L = 1,r = tot;LL sum = 0; while(L <= r) { if(dis[L]+dis[r] <= k) sum += r-L,L++; else r--; } return sum; } void divide(int u)//分治 { ans += slove(u,0); vis[u] = 1; for(int i = head[u];i;i = e[i].next) { int v = e[i].to,dis = e[i].dis; if(vis[v]) continue; ans -= slove(v,dis); sz = ssize[v]; mx = INF; findroot(v,0); divide(rt); } } int main() { while(n = read(),k = read(),n || k) { for(rg int i = 1;i <= n;++i) vis[i] = 0,head[i] = 0; cnt = 0; for(rg int i = 1;i < n;++i) { int x,y,z; x = read(),y = read(),z = read(); add(x,y,z);add(y,x,z); } mx = INF,sz = n,ans = 0; findroot(1,0); divide(rt);//从重心开始分治 printf("%lld ",ans); } system("pause"); } /* 11 10 1 2 1 2 4 1 2 5 1 1 3 1 3 6 1 4 7 1 4 8 1 5 9 1 6 10 1 6 11 1 */