lighthouse solution

· · 题解

定义一次操作 (u,j) 为在 u 的点权为 j 时给 u 的点权 +1。现在可以分别考虑计算每一个操作的贡献。

那么可以枚举操作 (u,j)，然后对于一个点 v，其能够对 (u,j) 的贡献产生贡献当且仅当树以 u 为根，执行该操作时 u\rightarrow v 的路径上所有点权均为 j。那么枚举这一操作何时执行，然后 v 到根这条链上的所有点必须在这一操作之前占据 j 个位置，剩下的位置从剩余的点里面瞎选操作就可以了。该操作执行后从所有点里面瞎选点操作就可以了。得到下式：

\text{Ans}=\sum_{u=1}^n\sum_{v=1}^n\sum_{j=0}^{m-1}\sum_{i=0}^{m-1}\dfrac{(dj)!}{(j!)^d}\cdot\dbinom{i}{dj}(n-d)^{i-dj}n^{m-i-1}

其中 d 是 u\rightarrow v 路径上点的数量。

提一提公因式：

\text{Ans}=n^{m-1}\sum_{u=1}^n\sum_{v=1}^n\sum_{j=0}^{m-1}\dfrac{(dj)!}{(j!)^d(n-d)^{dj}}\sum_{i=0}^{m-1}\cdot\dbinom{i}{dj}\left(\dfrac{n-d}{n}\right)^i

考虑提前对于所有 d ，预处理出路径上点数为 d 的点对数，记为 C_d。

\text{Ans}=n^{m-1}\sum_{d=1}^nC_d\sum_{j=0}^{m-1}\dfrac{(dj)!}{(j!)^d(n-d)^{dj}}\sum_{i=0}^{m-1}\cdot\dbinom{i}{dj}\left(\dfrac{n-d}{n}\right)^i

然后需要快速计算：

f_{a,b}=\sum_{i=0}^{m-1}\dbinom{i}{a}\left(\dfrac{n-b}{n}\right)^i

套路组合数加法递推：

f_{a,b}=\sum_{i=0}^{m-1}\dbinom{i-1}{a-1}\left(\dfrac{n-b}{n}\right)^i+\sum_{i=0}^{m-1}\dbinom{i-1}{a}\left(\dfrac{n-b}{n}\right)^i f_{a,b}=\sum_{i=0}^{m-2}\dbinom{i}{a-1}\left(\dfrac{n-b}{n}\right)^{i+1}+\sum_{i=0}^{m-2}\dbinom{i}{a}\left(\dfrac{n-b}{n}\right)^{i+1} f_{a,b}=\dfrac{n-b}{n}\left[f_{a-1,b}-\dbinom{m-1}{a-1}\left(\dfrac{n-b}{n}\right)^{m-1}\right]+\dfrac{n-b}{n}\left[f_{a,b}-\dbinom{m-1}{a}\left(\dfrac{n-b}{n}\right)^{m-1}\right] \dfrac{b}{n}f_{a,b}=\dfrac{n-b}{n}f_{a-1,b}-\dbinom{m-1}{a-1}\left(\dfrac{n-b}{n}\right)^{m}-\dbinom{m-1}{a}\left(\dfrac{n-b}{n}\right)^{m} f_{a,b}=\dfrac{n-b}{b}f_{a-1,b}-\dfrac{n}{b}\dbinom{m-1}{a-1}\left(\dfrac{n-b}{n}\right)^{m}-\dfrac{n}{b}\dbinom{m-1}{a}\left(\dfrac{n-b}{n}\right)^{m} f_{a,b}=\dfrac{n-b}{b}f_{a-1,b}-\dfrac{n}{b}\dbinom{m}{a}\left(\dfrac{n-b}{n}\right)^{m}

这样这个东西就可以递推了。既然 b 只有 O(n) 种，我们就可以在枚举到一个 d 的时候递推一遍，然后剩下的暴力算可以做到 O(nm+m\ln m)，足以通过。

可以通过点分治和分块多点求值做到 O(n\log^2n+m\log^3m+m\sqrt m\log m)，然而由于常数原因没啥用。