85 C Petya and Tree

問題

二分探索木（あるノードの左の子孫のノードは、すべて値がそのノードの値より小さく、右の子孫のノードは値がそのノードの値より大きい二分木）で、全てのノードの子ノードの数は0または2であるものが与えられる。

この木で、与えられた値に対して、通常の二分木の探索のように探索を行う。
ただし、探索の途中で一度だけ大小判定を間違ってしまう。
そのような誤りは、全て等しい確率で起こる。

このとき、辿り着く葉のノードの値の期待値を求めよ。

制約条件

n≦10^5
クエリの数≦10^5

方針

なんか上手く言語化できない。

大小比較を間違うのは必ず一回であるため、間違える箇所を決めれば辿り着くノードは一意に定まる。
どこで間違ったかが決まった後、どこに着くかを求めるのは、頂点を愚直に辿るとO(n)時間かかる。
が、「大きい」というところを「小さい」と誤判定したら、以後の判定は全て「大きい」になり、逆も同じなので、そのノードの右側のうち最も小さい葉をDPにより前計算しておくことでO(1)で計算できるようになる。

しかしこれでは一回のクエリにO(n)時間かかる。
本来の辿り着く葉がAであるようなクエリと、本来辿り着く葉がBであるようなクエリがあったとする。
ここでA,Bが同じ親をもっていたとすると、期待値の計算はほとんどの部分が同じであることがわかる。
よってこの部分が計算量を落とせそうである。

実際に、「ある頂点から、その親の頂点以降の期待値を求める関数」がメモ化でき、
これによりO(n)の前処理により、全ての葉について期待値がO(1)時間で求められるようになる。

では、本来辿り着く葉をどうやって求めるか。これも愚直にやるとO(n)時間がかかってしまう。
自分は以下のようにしてO(log n)時間で求めた。
クエリの値をxとする。

xより小さい最大の値を持つ葉をA,xより大きい最小の値を持つ葉をBとすると、本来辿り着く葉はAまたはBのどちらかである。
これがどちらであるかは、AとBの最小共通先祖のノード（これをCとする）の値とxを比較して、小さいならA,大きいならBと決定できる。
AとBはあらかじめ葉のノードを列挙してソートしておくなどして、二分探索によりO(log n)時間で求められる。

共通祖先のノードは、色々な方法があるが、蟻本の271ページの方法でO(log n)時間で求めた。

以上から、全体でO((n+q) log n)時間で全ての計算がおこなえて、制限時間に間に合う。

ソースコード

const int MAX_N = 100000;
int n,k,lch[MAX_N],rch[MAX_N],p[MAX_N],val[MAX_N];
int parent[20][MAX_N];
int depth[MAX_N],mx[MAX_N],mn[MAX_N];
vector<pi> leaves;
map<int,int> val_to_v;

double dp[MAX_N][2],ans[MAX_N];
double calc(int node,int cld){
	if(dp[node][cld]>0)return dp[node][cld];
	
	double &ret=dp[node][cld];
	ret=0;
	if(p[node]>=0)ret+=calc(p[node],val[node]>val[p[node]]);
	if(cld==0)ret+=mn[rch[node]];
	else ret+=mx[lch[node]];
	return ret;
}
void dfs(int c,int d){
	depth[c]=d;
	if(lch[c]<0){
		leaves.pb(mp(val[c],c));
		mx[c]=mn[c]=val[c];
		return;
	}
	dfs(lch[c],d+1); dfs(rch[c],d+1);
	mx[c]=max(mx[lch[c]],mx[rch[c]]);
	mn[c]=min(mn[lch[c]],mn[rch[c]]);
	
}
int lca(int u,int v){
	if(depth[u]>depth[v])swap(u,v);
	rep(k,20){
		if((depth[v]-depth[u])>>k&1)v=parent[k][v];
	}
	if(u==v)return u;
	for(int k=19;k>=0;k--){
		if(parent[k][u]!=parent[k][v]){
			u=parent[k][u];
			v=parent[k][v];
		}
	}
	return parent[0][u];
}

void run()
{
	scanf("%d",&n);
	rep(i,n)lch[i]=rch[i]=-1, mx[i]=-inf, mn[i]=inf;
	depth[0]=0;
	int root;
	
	rep(i,n){
		scanf("%d%d",p+i,val+i); p[i]--;
		parent[0][i]=p[i];
		val_to_v[val[i]]=i;
		
		if(p[i]>=0){
			if(val[i]<val[p[i]])lch[p[i]]=i;
			else rch[p[i]]=i;
		}
	}
	rep(i,n){
		if(p[i]>=0){
			if(val[i]<val[p[i]])lch[p[i]]=i;
			else rch[p[i]]=i;
		}
		else root=i;
	}
	dfs(root,0);
	
	for(int k=0;k+1<20;k++)rep(v,n){
		if(parent[k][v]<0)parent[k+1][v]=-1;
		else parent[k+1][v]=parent[k][parent[k][v]];
	}
	rep(i,n)if(lch[i]<0){
		ans[i]=calc(i,val[i]>val[p[i]])/depth[i];
	}
	
	const int leaf=leaves.size();
	sort(all(leaves));
	int k; scanf("%d",&k);
	rep(i,k){
		int x,lo=-1,hi=leaf,mid;
		scanf("%d",&x);
		while(lo+1<hi){
			mid=(lo+hi)/2;
			if((mid<0?-inf:mid<leaf?leaves[mid].first:inf)<x)lo=mid; else hi=mid;
		}
		//cerr<<"lo: "<<lo<<" hi: "<<hi<<endl;
		if(hi==leaf)x=leaves[leaf-1].second;
		else if(lo==-1)x=leaves[0].second;
		else{
			lo=leaves[lo].second; hi=leaves[hi].second;
			mid=lca(lo,hi);
			if(x<val[mid])x=val_to_v[mx[lch[mid]]];
			else x=val_to_v[mn[rch[mid]]];
		}
		printf("%.9f\n",ans[x]);
	}
}