[Codeforces] 894D. Ralph And His Tour in Binary Country

題目連結:http://codeforces.com/problemset/problem/894/D

---

看了題解又問了人才會這題QAQ
本題作法我覺得好暴力(?，首先要觀察出這題第$i$條邊固定連接$ \lfloor \frac{i+1}{2} \rfloor $跟$i+1$的話，那給定的這棵樹就一定會是一棵完滿二元樹，深度必定為$\log_2(n)$，接著我們要預處理這棵樹，把每個點到其子樹們（包含自己）的距離算出來並排序好（這裡可以用merge sort的merge方法把兩棵子樹merge好），那我們要查詢的時候就只要往上走，並把我另外一邊的子樹可以走到的節點們通通加起來就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
typedef pair<lld,int> PLI;
#define FF first
#define SS second
const int N = 1000000 + 5;

vector<lld> dis[N], sum[N];
lld len[N];

void build(int,int);
lld go(int,lld,int);
PLI get_val(int,lld);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, q; cin>>n>>q;
	for(int i=2;i<=n;i++) cin>>len[i];
	build(1, n);
	while(q--){
		int w, l; cin>>w>>l;
		cout<<go(w, l, n)<<'\n';
	}
	return 0;
}

void build(int id, int mx){
	if(id > mx) return;
	
	const int lc = id*2, rc = id*2+1;
	auto& me = dis[id];
	const auto& L = lc<=mx ? dis[lc] : dis[0];
	const auto& R = rc<=mx ? dis[rc] : dis[0];

	build(lc, mx);
	build(rc, mx);

	me.PB(0);

	int pos=SZ(me), pos1=0, pos2=0;
	me.resize(SZ(me)+SZ(L)+SZ(R));
	while(pos1<SZ(L) and pos2<SZ(R)){
		if(L[pos1]+len[lc] < R[pos2]+len[rc]) me[pos++] = L[pos1++]+len[lc];
		else me[pos++] = R[pos2++]+len[rc];
	}
	while(pos1 < SZ(L)) me[pos++]=L[pos1++]+len[lc];
	while(pos2 < SZ(R)) me[pos++]=R[pos2++]+len[rc];

	auto& mys = sum[id];
	mys.resize(SZ(me));
	for(int i=0;i<SZ(me);i++) mys[i]=me[i];
	for(int i=1;i<SZ(me);i++) mys[i]+=mys[i-1];
}

lld go(int w, lld h, int n){
	PLI fq = get_val(w, h);
	lld cnt = fq.SS-1, sm = fq.FF, hh=h;
	int prew = -1;
	while(hh > 0 and w > 0){

		lld rs = 0, rc = 0;
		if(prew != -1 and (prew^1)<=n){
			PLI tmp = get_val(prew^1, hh-len[prew^1]);
			rc=tmp.SS;
			rs=tmp.FF+((h-hh)+len[prew^1])*rc;
		}
		cnt += rc+1, sm += rs+(h-hh);

		prew = w;
		hh -= len[w], w >>= 1;
	}
	return h*cnt - sm;
}

PLI get_val(int w, lld h){
	auto& dd = dis[w];
	auto it = upper_bound(ALL(dd), h);
	int sz = it-dd.begin()-1;
	if(sz < 0) return {0, 0};
	return {sum[w][sz], sz+1};
}