USACO 2012 December Gold - Running Away from the Barn

問題文 : Running Away from the Barn

問題概要 :
大きさ$N$ の木が与えられる. 距離が$L$ 以内の自分の子孫に当たるノードの個数を, すべてのノードについて求めよ.
$N \leqq 200000$

解法 :
行きがけ順で木を列にして, BIT で管理するという常套手段を使う.
入っていく(下方向の) ノードはノードの個数+1, 上がっていく方は-1 として, いもす法っぽく処理する.

コード :

#include <cstdio>
#include <vector>

using namespace std;
typedef long long lint;

struct Edge {
	int to;
	lint cost;
	Edge(int to, lint cost) : to(to), cost(cost){}
	Edge(){}
};

vector<Edge> G[200100];
lint dist[200100];
int idx[200100];
int vis[400100], id[400100];
int bit[400100];

int N;
lint L;

void add(int k, int x)
{
	if (!k) return;
	while (k < 400100){
		bit[k] += x;
		k += k & -k;
	}
}

int sum(int k)
{
	int ret = 0;
	while (k){
		ret += bit[k];
		k &= (k - 1);
	}
	return (ret);
}

void dfs(int v, lint l, int d, int &k)
{
	dist[d] = l;
	idx[d] = v;
	
	vis[v * 2] = k++;
	
	int lo = 0, hi = d, mid = 0;
	
	while (lo != hi){
		mid = (lo + hi) >> 1;
		if (l - dist[mid] <= L){
			hi = mid;
		}
		else {
			lo = mid + 1;
		}
	}
	
	mid = (lo + hi) >> 1;
	add(vis[idx[mid] * 2], 1);
	add(vis[v * 2] + 1, -1);
	
	for (int i = 0; i < G[v].size(); i++){
		dfs(G[v][i].to, l + G[v][i].cost, d + 1, k);
	}
	
	vis[v * 2 + 1] = k++;
}

int main()
{
	freopen("runaway.in", "r", stdin);
	freopen("runaway.out", "w", stdout);
	
	scanf("%d %lld", &N, &L);
	
	for (int i = 1; i < N; i++){
		int a; lint b;
		scanf("%d %lld", &a, &b);
		G[--a].push_back(Edge(i, b));
	}
	
	int k = 1;
	dfs(0, 0, 0, k);
	
	for (int i = 0; i < N; i++){
		printf("%d\n", sum(vis[i * 2]) - sum(vis[i * 2 + 1]));
	}
	
	return (0);
}