题意:链接方法:树的点分治+DP解析:男八之一听完封禺讲完来刷然后发现有些地方是需要注意的！首先先说这个树树上的所有点分为两类一类是两个点间不经过根节点，另一类是经过根节点这里不经过根节点的显然递归求解即可我们只需要O(n)扫一下所有点到根节点的距离，然后用神♂奇的双指针判断一下有多少对就可以了，但是这样的话有可能有两个点在同一个根节点的子节点为根节点的子树里，也就是说这样的话我们会算多一部分，，只需要减掉子节点的计算就可以了。代码:#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 10010#define INF 0x3f3f3f3fusing namespace std;int n,k,cnt,root,tot;struct node{int from,to,next,val;}edge[N<<1];int head[N];int v[N];int siz[N];int fa[N];int dis[N];int ans;int val,G,total;void init(){ans=0;memset(v,0,sizeof(v));memset(head,-1,sizeof(head)),cnt=1;}void edgeadd(int from,int to,int val){edge[cnt].to=to,edge[cnt].next=head[from],edge[cnt].val=val;head[from]=cnt++;}void get_g(int now,int fa){siz[now]=1;int tmp=-1;for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(to==fa||v[to])continue;get_g(to,now);siz[now]+=siz[to];tmp=max(tmp,siz[to]);}tmp=max(tmp,total-siz[now]);if(tmp<val)val=tmp,G=now;}void dfsd(int u,int d,int fa){dis[++tot]=d;for(int i=head[u];i!=-1;i=edge[i].next){int to=edge[i].to;if(to==fa||v[to])continue;dfsd(to,d+edge[i].val,u);}}int calc(int u,int d){tot=0;dfsd(u,d,0);sort(dis+1,dis+1+tot);int pt1=1,pt2=tot,ret=0;while(pt1<pt2){while(dis[pt1]+dis[pt2]>k&&pt1<pt2)pt2–;ret+=pt2-pt1;pt1++;}return ret;}void dfs(int now){val=INF,total=siz[now]?siz[now]:n;get_g(now,0);ans+=calc(G,0);v[G]=1;for(int i=head[G];i!=-1;i=edge[i].next){int to=edge[i].to;if(v[to])continue;ans-=calc(to,edge[i].val);dfs(to);}}int main(){while(scanf(“%d%d”,&n,&k)&&n!=0&&k!=0){init();for(int i=1;i<n;i++){int x,y,z;scanf(“%d%d%d”,&x,&y,&z);edgeadd(x,y,z),edgeadd(y,x,z);}dfs(1);printf(“%d\n”,ans);}}
天不负;卧薪尝胆，三千越甲可吞吴。
