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;
}