[心得] CF771C sum over ceil(path length / k) on a tree rareone PTT批踢踢实业坊

[心得] CF771C sum over ceil(path length / k) on a tree

楼主: rareone (拍玄) 2019-03-31 15:19:47

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

继续阅读

[心得] CF1142B Greedy + RMQ + Pointer Jumpingrareone [心得] CF576C Mo's algorithm on non-DS problemrareone [问题] ZeroJudge-d688(已解决)fatcat8127 [心得] Codeforces 603Brareone Re: [问题] Big Oh running timeLPH66 [问题] Big Oh running timetriumphant10 [问题] DFS剪枝(已解决)fatcat8127 [问题] 三维偏序(已解决)fatcat8127 [问题] 一题现实中的问题GYLin Re: [问题] 乌龟塔问题ddavid