AGC047D Twin Binary Trees

非常水的红题，基本上可以说是一眼题！

对每个第二棵树的叶子，考虑维护根到这个叶子的树形结构，有点像动态开点线段树。

然后对第一棵树的每个叶子，把它和与它连边的点在连边的点的树形结构中记录这两个点到根路径上所有点的权值积。

接下来在第一棵树上做“线段树合并”，具体来讲是之前维护的树形结构的合并，由于是二叉树所以很类似于线段树合并。合并的时候相当于把左儿子和右儿子对应的所有点连边的点在第二棵树的结构拿出来合并。这个时候第一棵树的 LCA 是确定的，第二棵树可以在合并的时候 LCA 也是确定的，所以合并的时候乘上两个逆元作为系数即可。

整个东西非常像暴力写挂或者通道的边分树合并，但是好做非常多。。

复杂度应该和线段树合并一样，我觉得是 $O(n\log n)$ ，为啥题解是 $O(n\log^2 n)$ 。

写完就是榜 4 ！稍微卡了卡常就 Rank 2 只输直接输出答案的挂哥了！

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 1e6 + 10;
const int P = 1e9 + 7;
int n , h , tn;
int S[MAXN] , iv[MAXN] , A[MAXN];

int qm( int x ) {
    return x < P ? x : x - P;
}

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = ret * 1ll * x % P;
        x = x * 1ll * x % P , a >>= 1;
    }
    return ret;
}

int rt[MAXN] , tr[MAXN] , T[MAXN * 20] , ls[MAXN * 20] , rs[MAXN * 20] , fa[MAXN * 20] , cnt;
void build( int& r , int v , int val ) {
	r = ++ cnt;
	T[r] = val;
	if( v == 1 ) {
		return;
	}
	build( fa[r] , v >> 1 , val );
	if( v & 1 ) rs[fa[r]] = r;
	else ls[fa[r]] = r;
}

int ans;
int pre;
int merge( int rt , int r1 , int r2 ) {
	if( !r1 || !r2 ) return r1 | r2;
	int pv = iv[rt];
	pre = ( pre + ( T[ls[r1]] * 1ll * T[rs[r2]] + T[rs[r1]] * 1ll * T[ls[r2]] ) % P * pv ) % P;
	ls[r1] = merge( rt << 1 , ls[r1] , ls[r2] );
	rs[r1] = merge( rt << 1 | 1 , rs[r1] , rs[r2] );
	T[r1] = qm( T[r1] + T[r2] );
	return r1;
}

void solve( int R , int l , int r ) {
	if( l == r ) return;
	int m = l + r >> 1;
	solve( R << 1 , l , m ) , solve( R << 1 | 1 , m + 1 , r );
    pre = 0;
	rt[R] = merge( 1 , rt[R << 1] , rt[R << 1 | 1] );
    ans = ( ans + pre * 1ll * iv[R] ) % P;
}

void solve() {
	cin >> h;
//	h = 18;
	n = ( 1 << h ) - 1;
	tn = ( 1 << h - 1 );
	S[0] = iv[0] = 1;
	rep( i , 1 , n ) {
		S[i] = S[i >> 1] * 1ll * i % P;
		iv[i] = Pow( S[i] , P - 2 );
	}
    per( i , n , 1 ) {
        iv[i] = iv[i] * 1ll * iv[i >> 1] % P;
    }
	rep( i , 1 , ( 1 << h - 1 ) ) {
		scanf("%d",A + i);
//		A[i] = i;
	} 
	rep( i , tn , n ) {
		build( tr[A[i - tn + 1]] , A[i - tn + 1] + tn - 1 , S[A[i - tn + 1] + tn - 1] * 1ll * S[i] % P );
		int r = tr[A[i - tn + 1]];
		rep( j , 1 , h - 1 ) r = fa[r];
		rt[i] = r; 
	}
	solve( 1 , tn , n );
	cout << ans << endl;
}

signed main() {
//	 freopen("in","r",stdin);
	// freopen("fout","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}