CF竞赛题目讲解_CF791D(树上启发式合并)

// https://codeforces.com/contest/791/problem/D

// 树上启发式合并

// 如果小熊每次能跳跃的距离为1，那么问题变为求树上任意两点之间距离之和。

//   f[u][j]：  u子树中到根节点1的距离为j=dep(模k)的节点个数

// 树上任意两点间距离len=depth[x1]+depth[y1]-2*depth[f]，f表示点x1和点y1的最近公共祖先。

  //len = j + r - dep * 2  为节点j到节点r的路径长度，  节点j到根节点1的距离为j=dep(模k);

  // 如果len不是k的倍数，则加上       rev =( 2*k + dep * 2 -j-r) % k;  到总跳跃距离ans

// 总跳跃次数为： 总跳跃距离ans/k

// 4 3

// 1 2

// 1 3

// 2 4

//

// 

//