LG 3565 [POI2014]HOT-Hotels

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转树形 dp 长链剖分加强版先来考虑$1 \le n \le 5000$设$f[i][j]$表示在$i$的子树中与$i$距离为$j$的点数显然$f[i][j] = \sum f[to]j-1$设$g[i][j]$表示以$i$为根的子树中,点对$(x,y)$满足$x,y$到$lca(x,y)$距离都是$d$,并且$lca(x,y)$到$i$的距离为$d-j$的点对数$g[i][j] = \sum g[to][j+1]$$ans = \sum_{i=1}^n (g[i][0]+g[i][j] \times……