统计路径只管统计所有的即可 不用考虑减
可以用双指针统计!!!
也可用二分 麻烦一些 也更加满一些
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; int n,m,cnt,d[N],head[N],pos,siz[N],sum,x,y,z,ans,vis[N],t[5],root,maxson[N],k; struct Edge{int to,nex,v;}edge[N<<1]; void add(int a,int b,int c){edge[++pos]=(Edge){b,head[a],c};head[a]=pos;} void getroot(int x,int fa) { siz[x]=1;maxson[x]=0; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(vis[v]||v==fa)continue; getroot(v,x);siz[x]+=siz[v]; maxson[x]=max(maxson[x],siz[v]); } maxson[x]=max(maxson[x],sum-siz[x]); if(maxson[x]<maxson[root])root=x; } void getdis(int x,int fa,int val) { d[++d[0]]=val; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(vis[v]||v==fa)continue; if(val+edge[i].v>k)continue; getdis(v,x,val+edge[i].v); } } int calc(int x,int v) { d[0]=0;int ans=0; getdis(x,0,v); sort(d+1,d+1+d[0]); /* rep(i,1,d[0]) { int pos=upper_bound(d+1,d+1+d[0],k-d[i])-d-1; if(pos<1)continue;//注意特判 if(d[i]<=d[pos])ans+=pos-1; else ans+=pos; } *///两种写法都可以a 下面那种快一点 int l=1,r=d[0]; while(l<=r)(d[l]+d[r]<=k)?(ans+=r-l,++l):--r; return ans; } void solve(int x) { vis[x]=1;ans+=calc(x,0); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(vis[v])continue; ans-=calc(v,edge[i].v); root=0;sum=siz[v]; getroot(v,x); solve(root); } } int main() { scanf("%d",&n); rep(i,1,n-1) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z); scanf("%d",&k); sum=maxson[0]=n; root=0; getroot(1,0); solve(root); cout<<ans; return 0; }