?？透傎愵}目講解_旗鼓相當(dāng)?shù)膶κ?樹形DP)
2022-06-22 10:45 作者:Clayton_Zhou | 我要投稿
// https://ac.nowcoder.com/acm/contest/4853/E?
//使用樹形DP
//運(yùn)行時間(ms) 使用內(nèi)存(KB) 代碼長度 ?
//844 ???????????????? 229784 ???????? 1400
//?？透傎愵}目講解_旗鼓相當(dāng)?shù)膶κ?樹上啟發(fā)式合并)
//https://www.bilibili.com/video/BV1pL4y1F7Pc?spm_id_from=333.999.0.0
//?
//使用樹上啟發(fā)式合并
//運(yùn)行時間(ms) 使用內(nèi)存(KB) 代碼長度 ?
//197???????????????? 12172 ???????????? 1818
定義dp[u][j]為節(jié)點(diǎn)u為根的所有子樹中長度為j的路徑的條數(shù).? dp[u][0]=1 是為了后面的組合乘法
定義dpac[u][j]為節(jié)點(diǎn)u為根的所有子樹中長度為j的路徑端點(diǎn)權(quán)重之和.? dp[u][0]=?ac[u]
標(biāo)簽：
