Codeforces #358 Div2 C. Alyona and the Tree

ミスが多い。
http://codeforces.com/contest/682/problem/C

問題

根付き木が与えられる。
各頂点及び辺には値が振られている。
頂点vに対し、そのSubtree内の頂点uに対し、v→u間の最短路上の辺の値の合計が頂点uの値を超える、という事態を避けたい。
その事態を避けるため、いくつか頂点を減らしたい。
最小何個頂点を減らせばよいか。

解法

DFSで根から見ておき、各頂点vに対し、vの祖先の各頂点までの辺の総和の最大値を更新していく。
この最大値が頂点vの値を超えるなら、Subtree全体を減らさなければならない。

int N;
int A[101010];
int P[101010], C[101010];
vector<pair<int,int>> E[101010];
int did[101010];
int ret;

void dfs(int cur,ll cd,int del) {
	did[cur]=1;
	if(cd>A[cur]) del++;
	if(del) ret++;
	FORR(r,E[cur]) if(did[r.first]==0) dfs(r.first, max((ll)r.second,cd+r.second), del);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	for(i=1;i<N;i++) {
		cin>>P[i]>>C[i];
		P[i]--;
		E[i].push_back({P[i],C[i]});
		E[P[i]].push_back({i,C[i]});
	}
	dfs(0,0,0);
	
	cout<<ret<<endl;
}

まとめ

変な勘違いをしてWAを繰り返した。