AtCoder ARC #130 : D - Zigzag Tree

ほぼレート通りだった回。
https://atcoder.jp/contests/arc130/tasks/arc130_d

問題

木を成すN頂点のグラフが与えられる。
各頂点iに1～Nの異なる値P[i]を割り振ることを考える。
頂点a-b-cがパスを成しているときP[b]が最小値または最大値になるような割り振りは何通りか。

解法

f(v,n) := vのsubtreeについて考えるとき、v以下が問題の条件を満たし、かつvはvの子供よりも小さい値が割り振られていて、かつvのsubtree内でvがn番目に大きい値を割り振られている場合の組み合わせ
とする。
vの各子頂点cにおけるf(c,*)を定めると、木DPの要領で、vがcより大きい場合、vがsubtree内で取れる値の候補が何通りかは木DPで求めることができる。

g(v,n) := vのsubtreeについて考えるとき、v以下が問題の条件を満たし、かつvはvの子供よりも大きい値が割り振られていて、かつvのsubtree内でvがn番目に大きい値を割り振られている場合の組み合わせ
とすると対称性よりf(v,n)=g(v,S(v)-n) (S(v)はvのSubtreeの頂点数)となるので、結局fだけ考えればよい。

int N;
const ll mo=998244353;
vector<int> E[3030];
int C[3030];

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll dp[3050][3050];


void dfs(int cur,int pre) {
	ll from[3030]={};
	from[0]=1;
	C[cur]=1;
	int i,x,y;
	
	FORR(e,E[cur]) if(e!=pre) {
		ll to[3030]={};
		dfs(e,cur);
		ll DS[3030]={};
		
		FOR(x,N+1) {
			DS[x+1]=(DS[x]+dp[e][x])%mo;
		}
		FOR(x,C[cur]) FOR(y,C[e]) {
			(to[x+y]+=comb(x+y,x)*comb(C[cur]+C[e]-(1+x+y),C[cur]-(1+x))%mo*from[x]%mo*(mo+DS[N]-DS[y]))%=mo;
		}
		
		C[cur]+=C[e];
		swap(from,to);
	}
	
	FOR(i,C[cur]) dp[cur][i]=from[C[cur]-1-i];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,0);
	ll sum=0;
	FOR(i,N) sum+=dp[0][i];
	cout<<sum*2%mo<<endl;
}

まとめ

終了後門松列に反応した人を若干見た気がする。