CF771C Bear and Tree Jumps
赛时脑子抽了没想出来，其实思路已经沾边了，但是……唉，还是太菜了 qwq。
题意：
给你一颗有 \(n\) 个点的树，和每次能走的最大步数 \(K\)，求所有点对相互到达的最小步数之和。
思路：
首先第一步转化很简单：设点 \(u,v\) 在树上的距离为 \(d\)，则 \(u, v\) 相互到达的最小步数就是 \(\lceil \frac{d}{K} \rceil\)，因为每次我们都要尽量迈最大步数。这时我们很容易想到一种思路，那就是在 dfs 的过程中，去实现这个“逢 \(K\) 进一”。
我大概是卡在第二步转化的一半处。既然要进位，那我们可以考虑在状态中去记录余数。设状态 \(f_{u, j}\) ，表示所有距离点 \(u\) 距离为 \(j\) 的点的答案和，其中 \(j \in [0, K-1]\)，那么第一种转移很明显：
\[f_{u, j} = \sum f_{v, j-1}(j\in[1, K-1]) \]接下来我们考虑当 \(j = 0\) 时的答案。我们发现，对于距离 \(u\) 不超过 \(K\) 的点，因为必须要跳这一步，所有会产生 \(1\) 的贡献；对于距离超过 \(K\) 的点，则由于又走满了一个 \(K\)，故也会产生 \(1\) 的贡献。所以有：
\[f_{u, 0} = \sum (f_{v, K-1}+size_v) \]于是，我们可以求出根节点到所有的其他节点需要跳的步数和（就是 \(f_{1, 0}\)）。
但是，我们要求所有点对。所以第三步转化就是，我们进行换根 dp，转移和上面类似，注意剔除原来的贡献。我们求出以每个点为根的答案 \(g_{u, 0}\)，最后的答案就是：
\[\frac{1}{2}\sum_{i = 1}^{n} g_{i, 0} \]这里除以二是因为我们不考虑节点顺序，所以每对点都重复统计了一次。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
inline int read(){
int x = 0; char ch = getchar();
while(ch<'0' || ch>'9'){ch = getchar();}
while(ch>='0'&&ch<='9'){x = x*10+ch-48; ch = getchar();}
return x;
}
int head[N], tot = 1;
struct node{
int nxt, to;
}edge[N<<1];
void add(int u, int v){
edge[++tot].nxt = head[u];
edge[tot].to = v;
head[u] = tot;
}
int n, K;
long long dp[N][7], siz[N], g[N][7];
void dfs1(int u, int fa){
siz[u] = 1;
for(int i = head[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if(v == fa) continue;
dfs1(v, u);
siz[u]+=siz[v];
for(int j = 1; j<=K; ++j){
dp[u][j%K] += dp[v][j-1];
if(j == K) dp[u][0]+=siz[v];
}
}
}
void dfs2(int u, int fa){
for(int i = head[u]; i; i = edge[i].nxt){
int v = edge[i].to;
if(v == fa) continue;
for(int j = 1; j<=K; ++j){
int ta = j-2;
if(j==1) ta = K-1;
g[v][j%K] += (dp[v][j%K]+g[u][j-1]-dp[v][ta]);
if(j==1) g[v][j%K]-=siz[v];
if(j==K) g[v][j%K]+=(n-siz[v]);
}
dfs2(v, u);
}
}
long long ans;
int main(){
n = read(), K = read();
for(int i = 1; i<n; ++i){
int u = read(), v = read();
add(u, v);
add(v, u);
}
dfs1(1, 0);
for(int i = 0; i<K; ++i){
g[1][i] = dp[1][i];
}
dfs2(1, 0);
for(int i = 1; i<=n; ++i) ans+=g[i][0];
printf("%lld\n", ans/2);
return 0;
}