题目链接 Bear and Tree Jumps
考虑树形DP。$c(i, j)$表示$i$最少加上多少后能被$j$整除。
在这里我们要算出所有$c(i, k)$的和。
其中$i$代表每个点对的距离，$k$为输入的$k$值。
$f[i][j]$表示以$i$为根结点，深度对$k$取模为$j$的点的个数。
状态转移时$f[x][i]$一边更新一边和刚刚计算出的$f[u][j]$统计答案。
具体细节可以看代码。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) const int N = ;
int n, k;
long long sum[N], f[N][], ans = ;
vector <int> v[N]; void dfs(int x, int fa, int dep){
f[x][dep % k] = sum[x] = ; //初始化
for (auto u : v[x]){
if (u == fa) continue;
dfs(u, x, dep + );
rep(i, , k - ) rep(j, , k - ){
int dis = ((i + j) % k - ((dep * ) % k) + k) % k;
int t = ( * k - dis) % k;
ans += t * f[x][i] * f[u][j]; //这一步求出要被k整除则还需补多少的总和 （1）
} rep(i, , k - ) f[x][i] += f[u][i];
sum[x] += sum[u];
ans += (n - sum[u]) * sum[u]; //若没有（1）则这一步求的是树上所有点两两距离和 （2）
}
} int main(){ scanf("%d%d", &n, &k);
rep(i, , n - ){
int x, y;
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
} dfs(, , );
printf("%lld\n", ans / k); //最后除以k
return ;
}