题目大意
给定一棵树，边带权，问有多少点对满足二者间距离$leq K$,$n leq 40000$.
题解
点分治专题首杀！$Jackpot!$
(本来看着题意比较简单想捡个软柿子捏，结果手断了……)
点分治的总结先鸽着，这里只说题解。
分析一下题目：
对于无根树上的某一节点x，如果把它看作根，树上的路径无非两类：
1.经过x。
2.不经过x，但在它的子树里。
显然，后者利用点分治的思想经过递归处理可以转化为前者，那么我们就只需考虑第一类，
这也是点分治的强大之处。
我们设$dis[]$为节点到根节点x的距离，那我们要求的就是所有点对$(i,j)$，满足：
$dis[i]+dis[j] leq K$，且$i,j$不位于同一子树内。
接下来我们想办法实现对$(i,j)$的查询。
我们可以先处理出一棵子树内的$dis[]$，然后对这颗子树进行操作：
对于每个节点u，查询权值前缀$(K-dis[u])$即为所求，可以用类似于桶的树状数组实现。
然后在桶中插入$dis[u]$，表示到跟距离为$dis[u]$的节点数增加1。
按道理来讲，这玩意用树状数组很好搞对叭？
但是我们要插入的权值是$dis[]$，这东西大起来可是完全可以撑爆数组下标的。
(似乎有人拿树状数组水过了？打脸声啪啪啪啪)
不过不要忘了还有一个大家耳熟能详的树锯结垢能实现插入权值、查询前缀和的操作：
平衡树
我们要查询的权值前缀和，不就是相当于查排名么？
之后也就剩点分治的套路了，找根递归处理什么的。
另外还有一些细节：
不要照搬普通平衡树的板子，必须和实际应用相结合。我们这里的查排名可不一定是用平衡树里的权值查，所以有必要先插入再删除。
而且，平衡树查的是不大于某个权值的数的量，不是查排名，所以getrank时没必要ans++。
(相等的也要算啊！是$leq$不是$<$,所以答案return前要$+cnt[now]$)
不仅如此，你先插入后查询会多一个，最后记得-1。
还有！点分治和平衡树都会有$size[],root$之类的变量，如果设置很多不同的变量名会很麻烦而且容易错，
这时候可以用C++的$namespace$，用法类似于结构体，只不过调用成员方式不是$.$而是$::$，
这样变量名重复就没关系了。
#define R #include<cstdio> #include<iostream> #include<cstring> using namespace std; const int N=80005; #ifdef R const int L=1<<20|1; char buffer[L],*S,*T; #define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++) #endif inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f; } namespace Splay { int fa[N],cnt[N],son[N][3],size[N],key[N],type,root; void clear(int x) { fa[x]=cnt[x]=son[x][0]=son[x][1]=size[x]=key[x]=0; } void up(int x) { if(x) { size[x]=cnt[x]; if(son[x][0])size[x]+=size[son[x][0]]; if(son[x][1])size[x]+=size[son[x][1]]; } } bool judge(int x) { return son[fa[x]][1]==x; } void rotate(int x) { int old=fa[x],oldf=fa[old],lr=judge(x); son[old][lr]=son[x][lr^1]; fa[son[old][lr]]=old; son[x][lr^1]=old; fa[old]=x; fa[x]=oldf; if(oldf)son[oldf][son[oldf][1]==old]=x; up(old);up(x); } void splay(int x) { for(int f;f=fa[x];rotate(x)) if(fa[f])rotate(judge(x)==judge(f)?f:x); root=x; } void ins(int x) { if(!root) { type++; key[type]=x; root=type; cnt[type]=size[type]=1; fa[type]=son[type][0]=son[type][1]=0; return ; } int now=root,f=0; while(1) { if(x==key[now]) { cnt[now]++; up(now);up(f); splay(now); return ; } f=now;now=son[now][key[now]<x]; if(!now) { type++; size[type]=cnt[type]=1; son[type][0]=son[type][1]=0; son[f][x>key[f]]=type; fa[type]=f; key[type]=x; up(f);splay(type); return ; } } } int getsum(int x) { int now=root,ans=0; while(1) { if(x<key[now])now=son[now][0]; else { ans+=size[son[now][0]];//puts("YOUSA");cout<<x<<' '<<now<<endl; if(x==key[now]) { ans+=cnt[now]-1; splay(now); return ans; } ans+=cnt[now]; now=son[now][1]; } } } int pre() { int now=son[root][0]; while(son[now][1])now=son[now][1]; return now; } void del(int x) { getsum(x); if(cnt[root]>1) { cnt[root]--; up(root); return ; } if(!son[root][0]&&!son[root][1]) { clear(root);root=0; return ; } if(!son[root][0]) { int old=root; root=son[root][1]; fa[root]=0; clear(old); return ; } else if(!son[root][1]) { int old=root; root=son[root][0]; fa[root]=0; clear(old); return ; } int old=root,L=pre(); splay(L); son[root][1]=son[old][1]; fa[son[old][1]]=root; clear(old); up(root); } } int n,tot,head[N],len[N<<1],nxt[N<<1],to[N<<1],K; int size[N],vis[N],maxx,root,sz,ans,dis[N],st[N],top; void add(int x,int y,int z) { to[++tot]=y; nxt[tot]=head[x]; len[tot]=z; head[x]=tot; } void cacl(int x,int fa) { st[++top]=dis[x]; Splay::ins(K-dis[x]); ans+=Splay::getsum(K-dis[x]); Splay::del(K-dis[x]); for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=fa)cacl(to[i],x); } void dfs(int x,int fa) { for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(vis[y]||y==fa)continue; dis[y]=dis[x]+len[i]; dfs(y,x); } } inline void groot(int x,int fa) { size[x]=1; int num=0; for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(y==fa||vis[y])continue; groot(y,x); size[x]+=size[y]; num=max(num,size[y]); } num=max(num,sz-size[x]); if(maxx>num)maxx=num,root=x; } void dac(int x) { maxx=0x3f3f3f3f,root=0; groot(x,0); x=root;dis[x]=0;vis[x]=1;top=0;Splay::root=Splay::type=0; dfs(x,0); if(head[x])Splay::ins(0); for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(vis[y])continue; cacl(y,x); if(nxt[i])while(top)Splay::ins(st[top--]); } for(int i=head[x];i;i=nxt[i]) { int y=to[i]; if(vis[y])continue; sz=size[y]; dac(y); } } int main() { n=read(); for(int i=1;i<n;i++) { int x=read(),y=read(),z=read(); add(x,y,z);add(y,x,z); } K=read();sz=n; dac(1); cout<<ans<<endl; return 0; }