Codeforces #447 Div2 D. Ralph And His Tour in Binary Country

なんか今回全体的に入力が多い。
http://codeforces.com/contest/894/problem/D

問題

ヒープ形状を成すグラフが与えられる。
各辺にはコストが設定されている。

頂点番号Aと初期値Hが与えられる。
頂点AからコストH以内である頂点に移動できた場合、(H-コスト)分のスコアが得られるとする。
移動可能な頂点における総スコアを求めよ。

解法

各頂点について、根頂点からの距離を求めておく。
その後、各頂点に関しSubTree内の全距離のソート済み配列と、その累積和を求めておこう。
そうすると、各頂点に到達時にその時点の残った値がわかれば、ソート済み配列を探索することでそこからさらにSubTree方向に移動する際の総スコアが求められる。

ただこれだと子方向はまとめて探索できても親方向は探索できない。
今回は形状がヒープであることを利用し、log(A)個のSubTree探索で済ませよう。

例えば今A=13とすると、親はA/2=6であり反対の子はA=12である。
よって13→6→12と移動したコストを除けば、あとは12のSubTreeに対し同様の処理でスコアの数え上げができる。
この状態では6以下のSubTreeの処理は終わっているので、同様に次は親の3へと辿り、反対の子である5のSubTreeを処理していく。

int N,M;
int U[1010101];
int D[1010101][2];
ll dist[1010101];
vector<int> V[1010101];
vector<ll> S[1010101];

ll tot(int pos,int left) {
	if(pos>N || left<=0) return 0;
	int x=lower_bound(ALL(V[pos]),left+dist[pos])-V[pos].begin();
	if(x==0) return 0;
	return (ll)(left+dist[pos])*x - S[pos][x-1];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	FOR(i,N+1) U[i]=D[i][0]=D[i][1]=1<<25;
	for(i=1;i<=N-1;i++) {
		scanf("%d",&x);
		U[i+1]=D[(i+1)/2][(i+1)%2]=x;
		dist[i+1]=dist[(i+1)/2]+x;
	}
	
	for(i=N;i>=1;i--) {
		V[i].push_back(dist[i]);
		if(i*2+1<=N) {
			x=y=0;
			while(x<V[i*2].size()||y<V[i*2+1].size()) {
				if(x==V[i*2].size()) {
					V[i].push_back(V[i*2+1][y++]);
				}
				else if(y==V[i*2+1].size()) {
					V[i].push_back(V[i*2][x++]);
				}
				else {
					if(V[i*2][x]<=V[i*2+1][y]) V[i].push_back(V[i*2][x++]);
					else V[i].push_back(V[i*2+1][y++]);
				}
			}
		}
		else if(i*2<=N) {
			FORR(v,V[i*2]) V[i].push_back(v);
		}
		ll a=0;
		FORR(v,V[i]) {
			a+=v;
			S[i].push_back(a);
		}
	}
	
	while(M--) {
		int A,H;
		scanf("%d%d",&A,&H);
		ll ret=tot(A,H);
		while(A>1) {
			x=A/2;
			H-=U[A];
			if(H<=0) break;
			ret+=H;
			
			if(A%2==1) ret+=tot(x*2,H-D[x][0]);
			else ret+=tot(x*2+1,H-D[x][1]);
			A /= 2;
		}
		cout<<ret<<endl;
		
	}
}

まとめ

N=10^5でいいと思うのだけどこんな入力増やす必要あるのかな。