Codeforces #336 Div1 D. Power Tree

方針は思いついてもそこからの実装で苦戦した。
http://codeforces.com/contest/607/problem/D

問題

根付き木を考える。
初期状態は根を示す頂点１つだけで構成される。
また各頂点は値を持つ。

以下のクエリを順次処理せよ。

• 新規頂点を点P[i]の子として追加する。またその頂点の値はV[i]である。
• 頂点U[i]のスコアを答えよ。

なお、頂点xのスコアは、頂点xの値及び子頂点のスコアの総和に対し、(子頂点数+1)を掛けたものとなる。

解法

根頂点のスコア計算において、各頂点の値が何倍分寄与するかを遅延評価SegTreeで管理していく。
このSubTreeでは、区間に対し同じ倍率を掛ける処理と、(倍率を適用した)区間の総和を求める処理を取れるようにしておく。

まずクエリを先読みし、全体をEuler Tourで番号を付け替えておく。

• 頂点追加処理
  • P[i]を追加する際parent(P[i])のSubTreeの範囲に対し、P[i]を追加する前のparent(P[i])の子頂点数がcならSubTree全体を(c+2)/(c+1)倍することで頂点追加による他頂点への影響を考慮できる。
• 頂点のスコア算出
  • SegTreeからU[i]のSubTreeに対応する区間の総和を取ろう。
  • ただしこの総和は、根頂点のスコア計算に寄与する値であり、U[i]から根頂点に至るまで何度も数倍される影響が(不要に)含まれてしまっている。
  • そこでU[i]から根に至るまで、値が何倍されるかを求め、SegTreeにおけるSubTreeの総和から割ればよい。この値計算もSegTreeで行える。

ll mo=1000000007;
ll rev(ll a) {
	ll r=1, n=mo-2;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

template<int NV> class SegTree {
public:
	vector<ll> mul,sum;
	SegTree(){sum.resize(NV*2); mul=vector<ll>(NV*2,1);};
	ll update(int x,int y,int v,int l=0,int r=NV,int k=1) {
		if(l>=r) return 0;
		if(x<=l && r<=y) {
			(mul[k]*=v)%=mo;
			(sum[k]*=v)%=mo;
			return sum[k];
		}
		else if(l < y && x < r) {
			ll ret=0;
			ret += update(x,y,v,l,(l+r)/2,k*2);
			ret += update(x,y,v,(l+r)/2,r,k*2+1);
			sum[k]=(sum[k*2]+sum[k*2+1])*mul[k]%mo;
			return ret*mul[k]%mo;
		}
		else {
			return 0;
		}
	}
};
SegTree<1<<20> st;

int Q,N;
vector<int> E[202020];
int QtoV[202020];
int T[202020],P[202020],V[202020],U[202020];

int id=1;
int L[202020],R[202020];
int NC[202020];

void dfs(int cur) {
	L[cur]=id++;
	FORR(r,E[cur]) dfs(r);
	R[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>V[1]>>Q;
	N=1;
	FOR(i,Q) {
		cin>>T[i];
		if(T[i]==1) {
			QtoV[i]=++N;
			cin>>P[N]>>V[N];
			E[P[N]].push_back(N);
		}
		else {
			cin>>U[i];
		}
	}
	dfs(1);
	r=L[1]+(1<<20);
	st.sum[r]=V[1]*st.mul[r]%mo;
	st.update(1,2,1);
	
	FOR(i,Q) {
		if(T[i]==1) {
			x = QtoV[i];
			y = P[x];
			ll mult=st.update(L[y],L[y]+1,1)*rev(V[y])%mo;
			NC[y]++;
			st.update(L[y],R[y],(NC[y]+1)*rev(NC[y])%mo);
			
			int r = L[x]+(1<<20);
			st.sum[r]=V[x]*st.mul[r]%mo;
			st.update(L[x],L[x]+1,1);
			
			
		}
		else {
			x = U[i];
			ll s=st.update(L[x],R[x],1);
			ll n1=st.update(L[x],L[x]+1,1)*rev(V[x])%mo;
			ll n2=NC[x]+1;
			cout<<(s*n2%mo*rev(n1)%mo)<<endl;
		}
	}
}

まとめ

正直面倒なだけであまり面白い問題ではないなぁ…。