输入

10 48
1 57
2 29
2 33
4 1
3 49
1 33
2 53
7 53
4 41

输出

2
4
1
3
1
1
1
1
1
1

代码

#include<bits/stdc++.h>
using namespace std;
int n, k;
struct node{
	int v;
	long long c;
};
vector<node> G[200005], IG[200005];
long long f[200005], dis[200005];
int dep[200005];
int bin[200005][20];
void dfs(int u, long long ndis, int ndep){
	dis[u] = ndis;
	dep[u] = ndep;
	for (auto p : G[u]){
		int v = p.v;
		long long c = p.c;
		dfs(v, ndis + c, ndep + 1);
	}
}
void binary_dp(){
	for (int i = 1; i <= 20; i++)
		for (int j = 1; j <= n; j++){
			if (j + (1 << i) > n)
				break;
			bin[j][i] = bin[bin[j][i - 1]][i - 1];
		}
}
void multi_fa(int u){
	int v = u;
	for (int i = 20; i >= 0; i--){
		int d1 = dis[bin[v][i]], d2 = dis[u];
	//	cout << d1 << " " << d2 << "\n";
		if (d2 - d1 <= k)
			v = bin[u][i];
	}
	if (!v)
		v = 1;
	f[bin[u][0]]++;
	cout << bin[u][0] << " - " << bin[v][0] << "\n";
	f[bin[v][0]]--;
}
int givef(int u){
	for (auto p : G[u])
		f[u] += givef(p.v);
	return f[u];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for (int i = 2; i <= n; i++){
		int u;
		long long w;
		cin >> u >> w;
		G[u].push_back({i, w});
		IG[i].push_back({u, w});
		bin[i][0] = u;
	}
	dfs(1, 0, 0);
	binary_dp();
	for (int i = 1; i <= n; i++)
		multi_fa(i);
	givef(1);
	for (int i = 1; i <= n; i++)
		cout << f[i] + 1 << "\n";
}