考察後、なかなか数字が合わず手間取った。
https://atcoder.jp/contests/abc264/tasks/abc264_h
問題
N頂点の根付き木が与えられる。
親頂点の方が、子頂点より小さい番号を持っている。
k=1～Nのそれぞれに対し、以下を答えよ。
1番～k番の頂点の部分集合及びその誘導部分グラフを考えたとき、1番の頂点を根とすると完全二分木を成すような頂点の選び方は何通りか。
解法
D(v) := v番の頂点の深さ
dp(v,d,k) := kに対し、v番の頂点のSubTreeのうち、高さ(d-D(v))の完全二分木を成す頂点の部分グラフの組み合わせ数
dp(1,*,k)の総和を、kごとに答えればよい。
元の根付き木に、k番の頂点を順次加えることを考える。
まず、完全二分木の高さは高々logN程度にしかならないので、D(k)＞logNであるようなk番の頂点は無視してよい。
その頂点を部分集合に含めてしまうと、完全二分木を作りようがないため、部分集合に含めない一択となる。
なので、そのようなkに対してはdp(1,d,k)=dp(1,d,k-1)となる。
D(k)≦logNであるkに対し、まずdp(k,D(k),k)=1となる。
以降、kの祖先となる頂点vに対し、dp(v,d,k-1)からdp(v,d,k)への差分を考えよう。
vの子頂点の順不同の対(u1,u2)に対し、dp(v,d,k-1)はdp(u1,d,k-1)*dp(u2,d,k-1)の総和となる。
vの子頂点のうちkをSubTree内にもつcは、dp(c,d,k)がdp(c,d,k-1)から更新されるはずである。
そこで、その更新差分を使い、dp(v,d,k-1)からdp(v,d,k)の更新差分を計算していこう。
int N; int P[303030]; vector<int> E[303030]; const ll mo=998244353; ll sum[303030][20]; ll dp[303030][20]; int D[303030]; void up(int cur,int c,int d,ll p,ll q) { ll p2=dp[cur][d]; ll q2=(sum[cur][d]-p+mo)*q%mo; (dp[cur][d]+=q2)%=mo; (sum[cur][d]+=q)%=mo; if(cur==0) return; up(P[cur],cur,d,p2,q2); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; for(i=1;i<N;i++) { cin>>P[i]; P[i]--; E[P[i]].push_back(i); D[i]=D[P[i]]+1; } dp[0][0]=1; cout<<1<<endl; for(i=1;i<N;i++) { if(D[i]<20) { dp[i][D[i]]=1; up(P[i],i,D[i],0,1); } ll ret=0; FOR(j,20) ret+=dp[0][j]; cout<<ret%mo<<endl; } }
まとめ
いつものABC Exより知識成分少な目？
