CodeForces 791D 题解

下午没讲清楚,那我再写一下好了……

k=1的已经讲过了,不再重复。
k>1时,也是先将k=1的答案S求出来,也讲过了。
显然正确答案不是S/k,肯定比它要大,应该是形如(S+F)/k的一个东西。
关键就是求F。
求F,其实就是是求这样几个子问题:
(1)在所有的路径中,路径长度 mod k = 0的有多少?
(2)在所有的路径中,路径长度 mod k = 1的有多少?
(k)在所有的路径中,路径长度 mod k = k-1的有多少?
为了求解它们,设f(u,i)表示以u为根的子树中,深度 mod k = i的点有多少个。
转移方程很简单:f(u,i)=∑f(u的子节点,i)
在dfs到节点u时,我们统计:
(1)在起点、终点的LCA为u的路径中,路径长度 mod k = 0的有多少?
(2)在起点、终点的LCA为u的路径中,路径长度 mod k = 1的有多少?
(k)在起点、终点的LCA为u的路径中,路径长度 mod k = k-1的有多少?
最后再把它们累加就行了。
为了求上面的问题,我们枚举起点,终点深度 mod k的值。
假设u的子节点有m个,分别为v1,v2,…,vm,当前枚举vp,起点在子树vp中,终点在前p-1棵子树中。
当我们枚举起点深度 mod k  = i,终点深度 mod k = j时,
所有这样的路径的长度 mod k的值都是一样的,为(i+j-2*depth(u)) mod k。
路径条数就不难想了,为
f(vp,i)*(f(v1,j)+f(v2,j)+…+f(vp-1,j))
当求得以上几个问题之后,做这几个操作:
(1)在起点、终点的LCA为u的路径中,路径长度 mod k = 0的,不做任何操作。
(2)在起点、终点的LCA为u的路径中,若路径长度 mod k = 1的有x条,则将答案加上x*(k-1)。
(3)在起点、终点的LCA为u的路径中,若路径长度 mod k = 2的有x条,则将答案加上x*(k-2)。
……
这样,起点、终点的LCA为u的路径就处理完了。
每个点都这样弄一遍(其实就是dfs一遍)之后,所有的路径都处理完了,这个时候你的ans变量的值就是S+F。
输出的时候除以k就好了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注