USACO 2012 December Contest Gold, Running Away From the Barn

N頂点の木が与えられるので各点について、距離がL以下かつ部分木に含まれる点の個数を出力せよ
(N <= 200000)

各点について距離L以内でどこまで上に上がれるかわかればimos法するだけになるのでダブリングで処理

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <climits>
using namespace std;

typedef long long ll;
typedef pair<int, ll> P;

//container util
//------------------------------------------
#define pb push_back
#define mp make_pair
#define fi first
#define se second

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

int n;
ll l;
ll d[200010];
vector<P> g[200010];
int par[200010][19];
int r[200010];

inline void build(int v, ll dep, int p){
    par[v][0] = p;
    d[v] = dep;
    rep(i, g[v].size()) build(g[v][i].fi, dep + g[v][i].se, v);
}

int main(){
    freopen("runaway.in", "r", stdin);
    freopen("runaway.out", "w", stdout);
    scanf("%d %lld", &n, &l);
    par[0][0] = -1;
    rep(i, n - 1){
	int p; ll len;
	scanf("%d %lld", &p, &len);
	--p;
	g[p].pb(mp(i + 1, len));
    }
    build(0, 0, -1);

    rep(i, 18){
	rep(j, n){
	    if(par[j][i] < 0) par[j][i + 1] = -1;
	    else par[j][i + 1] = par[par[j][i]][i];
	}
    }

    rep(i, n){
	int v = i;
	ll cur = 0;
	++r[v];

	for(int j = 18; j >= 0; --j){
	    if(par[v][j] == -1) continue;
	    if(cur + d[v] - d[par[v][j]] <= l){
		cur += d[v] - d[par[v][j]];
		v = par[v][j];
	    }
	}
	if(par[v][0] != -1) --r[par[v][0]];
    }
    for(int i = n - 1; i >= 0; --i) if(par[i][0] != -1) r[par[i][0]] += r[i];
    rep(i, n) printf("%d\n", r[i]);
    return 0;
}