题目大意：给定一棵 N 个节点的无根树，边有边权，统计树上边权和不大于 K 的路径数。
对于每条树上路径，对于每一个点来说，该路径只有经过该点和不经过该点两种情况，对于不经过该点的情况，可以转化成是否经过以该点为树根的子树节点的子问题，由此构成一个分治策略。
对于点分治来说，限制算法复杂度的瓶颈之一是递归的层数，即：子问题的数目。因此，为了避免树退化成一条链，应该每次选取一棵树的重心作为根节点，进行递归求解。层数可以控制在 \(O(logn)\) 级别。
在统计经过每一个点的路径数量时，采用的策略是由该点出发，记录下以该点为根的子树中的每个点到该点的距离，排序后用双指针直接扫描记录贡献。考虑到路径必须经过该点，即：对于同一棵子树中的节点贡献值必须减去，因此在分治子树问题之前，先减去子树内部路径对答案的贡献。
代码如下
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define pb push_back
using namespace std;
const int maxn=1e4+10;
int n,k,ans;
int sn,root,sz[maxn],f[maxn],dep[maxn];
bool vis[maxn];
vector<int> ret;
struct node{
int nxt,to,w;
node(int a=0,int b=0,int c=0):nxt(a),to(b),w(c){}
}e[maxn<<1];
int tot=1,head[maxn];
inline void add_edge(int from,int to,int w){
e[++tot]=node(head[from],to,w),head[from]=tot;
}
void getroot(int u,int fa){
sz[u]=1,f[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa||vis[v])continue;
getroot(v,u);
f[u]=max(f[u],sz[v]);
sz[u]+=sz[v];
}
f[u]=max(f[u],sn-sz[u]);
if(!root||f[u]<f[root])root=u;
}
void getdis(int u,int fa){
ret.pb(dep[u]);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(v==fa||vis[v])continue;
dep[v]=dep[u]+w;
getdis(v,u);
}
}
int calc(int u,int d){
dep[u]=d;
ret.clear();
getdis(u,0);
sort(ret.begin(),ret.end());
int cnt=0,l=0,r=ret.size()-1;
while(l<r){
if(ret[r]+ret[l]<=k)cnt+=r-l,++l;
else --r;
}
return cnt;
}
void dfs(int u){
vis[u]=1;
ans+=calc(u,0);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(vis[v])continue;
ans-=calc(v,w);
root=0,sn=sz[v],getroot(v,0);
dfs(root);
}
}
void read_and_parse(){
for(int i=1;i<n;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z),add_edge(y,x,z);
}
}
void solve(){
getroot(1,0);
dfs(root);
printf("%d\n",ans);
}
void init(){
memset(head,0,sizeof(head)),tot=1;
memset(vis,0,sizeof(vis));
root=ans=0,sn=n;
}
int main(){
while(scanf("%d%d",&n,&k)&&n&&k){
init();
read_and_parse();
solve();
}
return 0;
}
update at 2019.3.18