题意：现在有一棵树，每条边的长度都为1，然后有一个权值，求存在多少个(u,v)点对，他们的路劲长度 <= l, 总权重 <= w.
题解：
1.找到树的重心。
2.求出每个点到中心的长度和权值。
3.对所有点都询问出合法点的个数（包括同一颗子树）加到答案上。
4.对于每一棵子树内部都找到合法点的个数从答案中减去。
5.递归处理每一颗子树。
我们现在最大的问题就是怎么计算合法点的个数。
我们把点的信息记录下来之后，按照权重从小到达排序。
然后我们就可以用2个端点维护出 a[l].weight + a[r].weight <= d
这样对于l来说, [l+1,r]里面的所有点都满足权重的条件了。
然后就只需要询问 [l+1,r]里面的点的深度 <= l – deep[i]的个数了，对于这个个数我们用树状数组去维护这个信息，一开始我们把所有的点的深度都加到树状数组里面，然后每次端点移动位置的时候都把当前点的深度从树状数组中移除，这样我们维护出了一颗[ l+1 , r] 里面的点的深度信息了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 5e5 + ;
int n, len, w;
int tree[N];
int root, sz[N], mxr;
int vis[N];
int head[N], to[N*], nt[N*], ct[N*];
void add(int x, int v){
for(int i = x; i <= n && i; i += i & (-i))
tree[i] += v;
}
int query(int x){
int ret = ;
for(int i = x; i; i -= i&(-i))
ret += tree[i];
return ret;
}
void getW(int o, int u, int num){
sz[u] = ;
int mx = ;
for(int i = head[u]; ~i; i = nt[i]){
int v = to[i];
if(vis[v] || v == o) continue;
getW(u, v, num);
sz[u] += sz[v];
mx = max(mx, sz[v]);
}
if(o) mx = max(mx, num-sz[u]);
if(mx < mxr) mxr = mx, root = u;
}
//pll p[N];
struct Node {
int fi, se;
bool operator < (const Node & x) const {
if(fi == x.fi) return se < x.se;
return fi < x.fi;
}
}p[N];
LL cal(int l, int r){
if(l >= r) return ;
sort(p+l, p+r+);
LL ans = ;
for(int i = l; i <= r; i++) add(p[i].se, );
for(int L = l, R = r; L <= R; L++){
while(L < R && p[L].fi + p[R].fi > w) {
add(p[R].se, -);
R--;
}
add(p[L].se, -);
if(L >= R) break;
ans += query(max(, len-p[L].se));
}
return ans;
} int sum = ;
void Dfs(int o, int u, int deep, int w){
sz[u] = ;
++sum;
p[sum].fi = w;
p[sum].se = deep;
for(int i = head[u]; ~i; i = nt[i]){
int v = to[i];
if(v == o || vis[v]) continue;
Dfs(u, v, deep+, w+ct[i]);
sz[u] += sz[v];
}
}
LL ans = ;
void GG(int id, int num){
if(num == ){
return ;
}
mxr = inf;
getW(, id, num);
vis[root] = ;
int ls = ; sum = ;
for(int i = head[root]; ~i; i = nt[i]){
int v = to[i];
if(vis[v]) continue;
Dfs(, to[i], , ct[i]);
ans -= cal(ls, sum);
ls = sum + ;
}
sum++;
p[sum].fi = p[sum].se = ;
ans += cal(, sum);
//cout << query(n) << endl;
for(int i = head[root]; ~i; i = nt[i]){
int v = to[i];
if(vis[v]) continue;
GG(v, sz[v]);
}
}
int tot = ;
void add(int u, int v, int w){
to[tot] = v;
ct[tot] = w;
nt[tot] = head[u];
head[u] = tot++;
}
int main(){
memset(head, -, sizeof(head));
scanf("%d%d%d", &n, &len, &w);
int u, v, val;
for(int i = ; i <= n; i++){
u = i;
scanf("%d%d", &v, &val);
add(u, v, val);
add(v, u, val);
}
GG(, n);
printf("%I64d\n", ans);
return ;
}
