KUPC 2014 F - テレパシー

問題

二次元平面上にn匹きつねがいて、
位置が(x[i], y[i]), パワーがd[i].
（何度でも）i番目のきつねにコスト1を支払うとそのきつねのパワーを1上げることができる。

きつねi, jは(iのパワー)+(jのパワー)がi, jのユークリッド距離以上ならば通信できる。
直接通信したいきつね同士のグラフが、無向木で与えられるとき、
支払わなければならないコストの和の最小値を求めよ。

制約条件

n≦1000
座標の絶対値≦1000
d[i]≧0

方針

きつね間の距離は3000未満なので、一匹につき3000あげれば十分。
なので、木DPで、dp[i][j]をi番目を根とする部分木を条件が満たされる状態にするために、
i番目のきつねにはコストj「以上」を支払うとするときのコストの和の最小値とする。

これを更新するDPがO(n * 3000)でできる。
（iにj支払うとき、k番目の子に払うコストはdist_k - j以上であるため、dp[子k][dist_k-j]だけを見ればよいから）

ソースコード

int n, x[1000], y[1000];
int c[1000], d[1000];
ll dp[1000][3000];

vector<vi> e;
int dist[1000][1000];

void rec(int cur, int p){
	rep(i, e[cur].size()) if(e[cur][i] != p){
		int to = e[cur][i];
		rec(to, cur);
		dist[cur][to] = ceil(hypot(x[cur] - x[to], y[cur] - y[to]));
		dist[cur][to] -= d[cur] + d[to];
	}
	
	rep(i, 3000){
		ll sum = (ll)c[cur] * i;
		rep(j, e[cur].size()) if(e[cur][j] != p){
			
			int to = e[cur][j];
			sum += dp[to][max(0, dist[cur][to] - i)];
		}
		dp[cur][i] = min(dp[cur][i], sum);
		if(i) dp[cur][i] = min(dp[cur][i], dp[cur][i - 1] + c[cur]);
	}
	for(int i = 2999; i > 0; i--) dp[cur][i - 1] = min(dp[cur][i - 1], dp[cur][i]);
}

int main(){
	cin >> n;
	e.resize(n);
	
	rep(i, n) cin >> x[i] >> y[i];
	rep(i, n) cin >> d[i] >> c[i];
	rep(i, n - 1){
		int a, b; cin >> a >> b;
		a--; b--;
		e[a].pb(b);
		e[b].pb(a);
	}
	
	rep(i, n) rep(j, 3000) dp[i][j] = 1e18;
	rec(0, 0);
	
	
	ll ans = 1e18;
	rep(i, 3000) ans = min(ans, dp[0][i]);
	cout << ans << endl;
	
	return 0;
}