LG 4103 [HEOI2014]大工程

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转先来考虑普通的树型 dp 怎么做设$SZ_x$表示$x$的子树中有多少个查询点,$d_x$表示$x$的深度这些新通道的代价和考虑每条边要被统计多少次:假设$y$是$x$的某个子节点,$x\leftrightarrow y$会被统计$(k-SZ_y)\times SZ_y$次,(起点可以是$y$的子树中任一查询点,终点可以是$y$子树外的任一查询点,这样的话路径必然经过$x\leftrightarrow y$)那么贡献是$(d_y-d_x)\times (k-SZ_y)\times SZ_y$这些新通……