Luogu

BZOJ权限题

分析

树形DP。

首先有一个结论:树上三个点之间的距离相等,则一定存在一个点,使得这三个点到着个点的距离相等。

设$f[i][j]$表示以$i$为根的子树中距$i$为$j$的点的数量,$g[i][j]$表示以$i$为根的子树中,两个点到LCA的距离为$d$,并且他们的LCA到$i$的距离为$d−j$的点对数。

容易得到:

$\large f[i][j]=\sum f[son][j-1]$

$\large g[i][j]=\sum \Big(g[son][j+1]+f[i][j]\times f[son][i-1]\Big)$

边界为$f[u][0]=1$。

考虑如何统计答案。容易得到,$\large ans=\sum\limits_{u}\Big[\sum\limits_{i}(f[u][i]\times g[v][i+1]+f[u][i-1]\times g[v][i])+g[u][0]\Big]$,于是可以在dfs时顺便统计$ans$。

于是做完了。

最后修改:2019 年 09 月 24 日 08 : 59 PM