作者rareone (拍玄)
看板Prob_Solve
标题[心得] CF771C sum over ceil(path length / k) on a tree
时间Sun Mar 31 15:19:47 2019
AS TITLE
题干非常简单
Given a bidirectional tree and k
这题要算的就是 sum over ceil(length between any pair of vertice / k)
作法：
DP，每条 path 的贡献在他的 LCA 算好
我们可以把一条 path 拆成可以被 k 整除的部分跟余数
像这样，假设 k = 5
-----, -----, -----, -----, -----, -----, --
接着维护余数为 t 的 path 有几条，例子中 t = 2
以及 sum : 已经成为完整的长度为 k 的部分有几个，例子中是 sum = 6
接着就像算 sum over length of all pair of path
实作细节：
k 不会很大，所以我写 k^2 n 复杂度也没慢多少，而且比较好写
这题我用 struct 把操作包起来，写起来非常舒服
写了一个 shift method 实际上是 +1 的意思
Solution:
https://codeforces.com/contest/771/submission/52069290
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.114.216.110
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1554016795.A.61A.html