CF競賽題目講解_CF102832F(樹上啟發(fā)式合并+二進制拆分)
2022-06-03 11:06 作者:Clayton_Zhou | 我要投稿
// https://codeforces.com/gym/102832/problem/F
// 統(tǒng)計滿足條件 ai⊕aj=a_lca(i,j),? 的節(jié)點對信息i⊕j
因為是異或運算，只有當(dāng)前位一個為0一個為1才會對答案產(chǎn)生貢獻，因此我們可以把每個頂點標(biāo)號拆成一個17位的二進制數(shù)。?注意 2^17=131,072
// 類似于下題， ?？透傎愵}目講解_旗鼓相當(dāng)?shù)膶κ?樹上啟發(fā)式合并)，? 對一個分支統(tǒng)計完貢獻后，再添加它的信息cnt[dep]和sum[dep]? ?
// https://ac.nowcoder.com/acm/contest/4853/E??
標(biāo)簽：
