1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| #include <bits/stdc++.h> #define MAXN 40005 using namespace std; 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<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } struct node{ int to,len; }; vector<node>G[MAXN]; inline void AddEdge(int u,int v,int w){ G[u].push_back(node{v,w}); } int sz[MAXN],f[MAXN],root; int vis[MAXN];
void GetRoot(int u,int father,int tot){ sz[u]=1,f[u]=0; for (register int i=0;i<G[u].size();++i){ int v=G[u][i].to; if (v!=father&&!vis[v]){ GetRoot(v,u,tot); sz[u]+=sz[v]; f[u]=max(f[u],sz[v]); } } f[u]=max(f[u],tot-sz[u]); if (f[u]<f[root]) root=u; } int stk[MAXN],r; void GetDep(int u,int father,int dep){ stk[++r]=dep; for (register int i=0;i<G[u].size();++i){ int v=G[u][i].to,w=G[u][i].len; if (v!=father&&!vis[v]){ GetDep(v,u,dep+w); } } } int k; inline int Calc(int u,int w){ r=0; GetDep(u,0,w); sort(stk+1,stk+1+r); int sum=0; for (register int i=1;i<=r;++i){ sum+=upper_bound(stk+i,stk+1+r,k-stk[i])-stk-i-1; } return sum; } inline void NewRoot(int u,int sz){ root=0; GetRoot(u,0,sz); } int ans; void dfs(int u){ ans+=Calc(u,0); vis[u]=true; for (register int i=0;i<G[u].size();++i){ int v=G[u][i].to,w=G[u][i].len; if (!vis[v]){ ans-=Calc(v,w); NewRoot(v,sz[v]); dfs(root); } } }
int main(){ int n=read(); for (register int i=1;i<n;++i){ int u=read(),v=read(),w=read(); AddEdge(u,v,w); AddEdge(v,u,w); } k=read(); f[0]=n; NewRoot(1,n); dfs(root); printf("%d\n",ans); }
|