[心得] 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