AtCoder AGC #047 : D - Twin Binary Trees

これは本番解けてよかったね。
https://atcoder.jp/contests/agc047/tasks/agc047_d

問題

高さHの完全二分木が2つ与えられる。
二分木の各ノードは、1と書かれた点を根とし、kと書かれた点に(2*k)と(2*k+1)の2つの点が子として接続された状態になる。
この2つの二分木の葉に対し、互いに1:1で辺が接続されたとする。この辺を特殊辺と呼ぶことにする。

特殊辺を2つ使って構成される閉路において、閉路上のノードの数値の積の総和を求めよ。

解法

問題文の図の通り、上下に2つの二分木が並んでいる状態を考える。

特殊辺を2つ定めると、あとは2つの二分木それぞれで葉のLCAまでの経路を結んだパスが閉路を成すことになる。
そこで、上の二分木のうち葉以外の頂点kを総当たりし、LCAがkとなるケースを考えていこう。
初手でk-(2*k)を結ぶケースと、k-(2*k+1)を結ぶケースを考える。
以後それぞれで子をたどり葉までの数値の積を求めて行くのだが、その際初手で(2*k)と(2*k+1)どちらに遷移したかを覚えておく。

その後、それぞれ特殊辺で下の二分木の葉に遷移するので、その際特殊辺の遷移後に頂点番号順にソートしておく。
あとは、各頂点に対し、根に向けて徐々に移動していきながら数値の積を取っていこう。
もし下の二分木で葉から根に移動する際、2つの頂点から合流した場合、初手が(2*k)と(2*k+1)で異なる場合は、そこで閉路が1つ形成されるので両者の積を解に計上しよう。
初手が(2*k)と(2*k+1)で一致する場合は、両者の和を取って以後根まで処理を続ける。

上の二分木をO(2^H)個総当たりするが、均しで葉の合計選択回数はO(H*2^H)である。
よって全体でO(H^2*2^H)で済む。

int H,N;
int P[1<<19];
const ll mo=1000000007;
vector<pair<int,pair<ll,ll>>> V;
vector<pair<int,pair<ll,ll>>> V2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H;
	N=1<<H;
	FOR(i,N-1) {
		//x=i+1;
		cin>>x;
		P[(1<<(H-1))+i]=x+(1<<(H-1))-1;
	}
	//srand(time(NULL));
	//random_shuffle(P+(1<<(H-1)),P+(2<<(H-1)));
	//for(i=(1<<(H-1));i<1<<H;i++) cout<<i<<" "<<P[i]<<endl;
	
	
	ll ret=0;
	for(i=1;i<1<<(H-1);i++) {
		int cur=i;
		//cout<<i<<endl;
		V.clear();
		V.push_back({2*cur,{1LL*cur*(2*cur)%mo,0LL}});
		V.push_back({2*cur+1,{0LL,(2*cur+1)}});
		while(V[0].first<1<<(H-1)) {
			V2.clear();
			FORR(a,V) {
				V2.push_back({2*a.first,{a.second.first*1LL*a.first*2%mo,a.second.second*1LL*a.first*2%mo}});
				V2.push_back({2*a.first+1,{a.second.first*1LL*(a.first*2+1)%mo,a.second.second*1LL*(a.first*2+1)%mo}});
			}
			swap(V,V2);
		}
		FORR(v,V) {
			v.first=P[v.first];
			//cout<<v.first<<":"<<v.second.first<<":"<<v.second.second<<" -> ";
			v.second.first=v.second.first*v.first%mo;
			v.second.second=v.second.second*v.first%mo;
			//cout<<v.first<<":"<<v.second.first<<":"<<v.second.second<<endl;
		}
		sort(ALL(V));
		while(V.size()>1) {
			V2.clear();
			FOR(j,V.size()) {
				x=V[j].first/2;
				if(j+1<V.size() && V[j].first/2==V[j+1].first/2) {
					ret+=(V[j].second.first*V[j+1].second.second+V[j].second.second*V[j+1].second.first)%mo*x%mo;
					V2.push_back({x,{(V[j].second.first+V[j+1].second.first)*x%mo,(V[j].second.second+V[j+1].second.second)*x%mo}});
					j++;
				}
				else {
					V2.push_back({x,{V[j].second.first*x%mo,V[j].second.second*x%mo}});
				}
			}
			swap(V,V2);
			
		}
		//cout<<i<<" "<<ret<<endl;
	}
	cout<<ret%mo<<endl;
	
	
}

まとめ

Fはまだ解いてない。