voidgetrt(int x, int fa){ //找到当前子树的重心 tot[x] = 1; int nowmx = -inf; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (y == fa || vis[y]) continue; getrt(y, x); tot[x] += tot[y]; nowmx = max(nowmx, tot[y]); } nowmx = max(nowmx, nowsz - tot[x]); if (nowmx < mx) { mx = nowmx, rt = x; } }
int l, r, q[40005];
voidgetdis(int x, int fa){ //统计答案部分:找到当前子树中每个点到重心的距离 q[++r] = dis[x]; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (y == fa || vis[y]) continue; dis[y] = dis[x] + val[i]; getdis(y, x); } }
ll calc(int x, int d){ //统计答案的函数 l = 1, r = 0; dis[x] = d; getdis(x, 0); //计算当前子树中每个点到重心的距离 sort(q + 1, q + r + 1); //双指针算出多少对数字满足q[i]+q[j]<=k ll ret = 0; while (l < r) { if (q[l] + q[r] <= k) { ret += r - l, l++; } else r--; } return ret; }
voiddivide(int x){ //点分治函数 ans += calc(x, 0); //这是在统计x的答案 vis[x] = 1; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (vis[y]) continue; ans -= calc(y, val[i]); //这是在减去x的答案中不合法的部分 mx = inf; nowsz = tot[y]; getrt(y, 0); //这是在找y的子树的重心 divide(rt); //递归进入y } }
intmain(){ n = read(); init(); for (int i = 1; i < n; i++) { int u = read(), v = read(), w = read(); addedge(u, v, w); } k = read(); mx = inf; nowsz = n; getrt(1, 0); divide(rt); printf("%lld\n", ans); return0; }