ABC269 Ex. Antichain
Difficulty:3178
問題
頂点0を根とするN頂点の木がある。1からNの各Kついて、以下の条件を満たすような頂点の選び方を求めよ。
選ばれている頂点の祖先であって、選ばれているような頂点が存在しない。
解法
まず、$ O(N^2)解法を紹介する。
dp[i][j] = 頂点iの部分木の中から頂点をj個選び、条件を満たすような選び方の数
とする。簡単のため、dp配列を形式的べき級数（というか、多項式）として扱う。
要するにdp[i] = {dp[i][0],dp[i][1],...}を$ dp_i = dp_{i,0} + dp_{i,1}x + dp_{i,2}x^2...
として見る。
このとき、iの子の集合を$ S_iとすると、dpの遷移は
$ dp_i = (\prod_{j\in S}dp_j) +x
となる。このxは、頂点iを選ぶとした場合に対応している。頂点iを選ぶと、部分木に含まれるそれ以外の頂点は選ぶことができないので、1つだけ選ぶ方法となる。
これをDFSで実装するとTLEする。
実装
code:cpp
bool solve(){
LL(n);
vector<vector<ll>>g(n);
rep(i,1,n){
LL(p);p--;
}
[DFS(&(auto&&f,ll pos)->vector<mint>{ vector<mint>ret(1,1);
ret = convolution(ret,f(f,to));
}
if(ret.size()==1){
ret.push_back(1);
}
else{
}
return ret;
}),&n]{
auto ret = DFS(DFS,0);
rep(i,1,n+1){
if(i<ret.size())cout << reti.val() << "\n"; else cout << 0 << "\n";
}
cout << endl;
}();
return false;
}
解法つづき
さて、木DPを高速化していくことになる。
部分問題として以下の問題を考える。
頂点$ 1,2,3...Mがパスになっていて、パス上の頂点以外の頂点（$ M+1<= i<=Nであるような頂点$ i）について$ dp_iが求まっているとき、$ dp_0を求めよ。
パス上のどこの頂点を選択するかを考えればよい。
頂点$ iを選択したとき、$ iの部分木からはそれ以上選ぶことができないことを踏まえると、
$ dp_0 = \prod_{j = 0}^{i-1} \prod_{k \in S_j}dp_k
となる。これを全てのiに対して行う。また、パス上から選ばないパターンもある。もろもろを考慮すると、公式解説にもあるように
$ dp_0 = \sum_{i=1}^M(\prod_{j = 0}^{i-1} \prod_{k \in S_j}dp_k)x + \prod_{j = 0}^{M} \prod_{k \in S_j}dp_k
となる。詳しい説明は筆者の実力不足により放棄するが、たくさんの多項式を掛け算しているので分割統治を適用することができる。
さて、もとの問題に戻る。木DPをしながら、ある子を先ほどの部分問題におけるパスに含まれている頂点とみなせば、同じように解けそうだ。（日本語がわかりづらいが、次を読むとわかると思う）
ここで #HL分解 を考える。HL分解により、子をheavyなものとそうでないものに分類し、部分問題の解法を使って解くことができる。 DP遷移はむずいです、、、
上の式ではxがついている項とついていない項があるので、その2つを良い感じに管理しながらDPしていく。
#HL分解 は、パスに対するクエリを高速に処理するアルゴリズムとして有名だが、このようにHL分解した木の性質を使って問題を解くこともできるというのがこの問題の肝だと思う。 提出
code:cpp
const int N_max = 200000;
vector<vector<ll>>g(N_max);
//相互に呼び出しするのでプロトタイプ宣言しておく。
vector<vector<mint>> heavy(ll pos);
vector<mint>right(ll pos);
bool solve(){
LL(n);
rep(i,1,n){
}
vector<ll>sz(n,1);
//逆順にforを回して部分木のサイズを求め、隣接リストの0番目がheavy childになるようにする
//まあ根の部分木サイズなんてどうせnなので、根の部分に変な値が入るけどスルー
for(int i = n-1;i>=0;i--){
}
}
}
auto ans = right(0);
ans.resize(n+1);
rep(i,1,n+1){
cout << ansi.val() << "\n"; }
return false;
}
//親とつながる辺がheavy pathである頂点について
//F_n:頂点pos以下のheavy path上のgを管理する
vector<vector<mint>> heavy(ll pos){
if(gpos.size()==0)return vector<vector<mint>>(1,vector<mint>(1,1)); vector<vector<mint>>right_sum,ret = heavy(gpos0); for(auto it = gpos.begin()+1;it!=gpos.end();it++){ right_sum.push_back(right(*it));
}
//いつもの分割統治FFTで、rightな子たちの総積を求める
while(right_sum.size()>1){
vector<vector<mint>>tmp;
if(right_sum.size()%2==1){
right_sum.push_back({1});
}
for(int i = 0;i<right_sum.size();i+=2){
tmp.push_back(convolution(right_sumi,right_sumi+1)); }
swap(tmp,right_sum);
}
if(right_sum.size())ret.push_back(right_sum0); else ret.push_back(vector<mint>(1,1));
return ret;
}
//親とつながる辺がright pathである頂点について
//Fを全部かけて、fに直す（分割統治）
vector<mint>right(ll pos){
auto v = heavy(pos);
auto bunkatu = &(auto&&f,ll l,ll r){ if(l+1==r){
return make_pair(vector<mint>(1,1),vl); }
int m = (l+r)>>1;
//ここの式全然わからん、、、
//うまいことかけて、最後にxをかけるものをfirst、かけないものをsecondに置いている
vector<mint>ret1 = convolution(L1,R2);
if(ret1.size()<R1.size())ret1.resize(R1.size());
rep(i,R1.size())ret1i += R1i; return make_pair(ret1,convolution(L2,R2));
};
autor1,r2 = bunkatu(bunkatu,0,len(v)); r1.insert(r1.begin(),0);
if(r1.size()<r2.size())r1.resize(r2.size());
rep(i,r2.size())r1i += r2i; // deb("right",pos);
// for(auto i:r1)cout << i.val() << spa;
// cout << endl;
return r1;
}