Codeforces #926 : Div2 F. Sasha and the Wedding Binary Search Tree

これはボス問の割に余り難しくないな…。
https://codeforces.com/contest/1929/problem/F

問題

二分木が与えられる。
各点には[1,C]の範囲の整数値が設定可能で、初期状態で設定されている点とされていない点がある。
全点に整数値を設定したとき、この木が二分探索木になるものは何通りか。

解法

二分木の設定値をin-order順で並べて行き、その数列をXとする。
X[a]とX[b]が設定されていて、X[a+1]～X[b-1]が未設定の場合、X[a+1]～[b-1]はX[a]以上X[b]以下の値を昇順で取れるので、H(X[b]-X[a]+1,b-a-1)通りの値を取れることになる。
未設定の値の区間ごとに、上記値の積を取ればよい。

int T,N,C;
int L[502020],R[502020],V[502020];

vector<pair<int,int>> X;
const ll mo=998244353;

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

ll comb(ll P_,ll Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	ll p=1,q=1;
	Q_=min(Q_,P_-Q_);
	P_%=mo;
	for(int i=1;i<=Q_;i++) p=p*P_%mo, q=q*i%mo,P_--;
	
	return p*modpow(q,mo-2)%mo;
}

ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

void dfs(int cur) {
	if(cur==-1) return;
	
	dfs(L[cur]);
	if(V[cur]==-1) {
		X.back().second++;
	}
	else {
		X.push_back({V[cur],0});
	}
	dfs(R[cur]);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>C;
		FOR(i,N) {
			cin>>L[i+1]>>R[i+1]>>V[i+1];
		}
		X={{1,0}};
		dfs(1);
		X.push_back({C,0});
		ll ret=1;
		FOR(i,X.size()-1) {
			if(X[i].first>X[i+1].first) ret=0;
			else ret=ret*hcomb(X[i+1].first-X[i].first+1,X[i].second)%mo;
		}
		cout<<ret<<endl;
	}
}

まとめ

なんだったんだろ…。