上来先留个心眼看看模数是不是质数
是质数啊那没事了
注意到值域和节点数量都相当小。这引导我们去枚举某个节点或某个值。
我们枚举潜入的城市 /(u/)，找出 /(d_v/) 比 /(d_u/) 大的所有 /(v/)。
可以知道我们要选的一定是一个连通块，这个连通块中只能恰好包括 /(k-1/) 个 /(v/)。
这有点像背包。于是我们将这种 /(v/) 节点的权值设为 /(x/)，别的节点权值全部设为 /(1/)。
计算所有包含 /(u/) 的联通块的权值之和，是一个多项式，然后取 /([x^k]/) 就行了。
而多项式在转移时自带一个 /(n^2/) 的复杂度，这可不好。
考虑一个可以间接去掉多项式乘法的方法：插值。
带入点值就很简单了。现在的操作变为：单点修改，求包含某个点的联通块的权值之和。插值是可以做到 /(O(n)/) 的，所以能做到 /(O(n^2f(n))/)，/(f(n)/) 是这个数据结构操作的复杂度。
这是一个显然的 DDP，转移方程为 /(f[u]=(/prod f[v])val[u]+1/)。
可以使用 LCT，不过常数巨大（）
瞟了一眼标签，感觉很牛逼啊！
考虑对于同一棵树的问题一起解决。也就是离线。其实整道题和动态也没有什么关系
设 /(f[u][k]/) 是第 /(k/) 次修改前的 /(f[u]/)，那么这个东西可以使用线段树来进行整体合并。
发现要做的操作只有后缀乘和全体加。于是就 /(O(n^2/log n)/) 了。
不知道比 LCT 快到哪里去了。
原创文章，作者：jamestackk，如若转载，请注明出处：https://blog.ytso.com/271703.html