题意：给出一棵树和一个数 k ，每一步最多走k条边，定义f(s,t)为从点s到点t需要走的最少步数。求所有点对f()的和。
tags：看学长题解码的，其实还是没太搞懂。。 （趁机膜我晏学长一发 传送门）
看到一个题解，讲的更详细点，传送门
总体思路：（1）如k=1，容易求出答案，设为s1。 （2）k>1时，答案为((s1+∑f(l,k))/k。f(l,k)指的是某个路径长度为l，然后让它能够被k整除还要加上几。 这里的f(l,k)用树dp，可O(n)O(k^2)求出，具体怎么求出来的没太搞懂，22333。。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 200005; vector<int >G[N]; ll dp[N][10], fs[N][10], ans; int n, k, a, b; void dfs(int u, int fa) { dp[u][0]=1; for(auto v : G[u]) if(v!=fa) { dfs(v, u); rep(i,0,k) rep(j,0,k) { //O(k^2)枚举出两端深度为k的求余结果 if(dp[u][i]==0 || dp[v][j]==0) continue; ll tmp=i+j+1; if(tmp%k) tmp=tmp/k+1; else tmp=tmp/k; ans+= tmp*dp[u][i]*dp[v][j]+fs[u][i]*dp[v][j]+fs[v][j]*dp[u][i]; } rep(i,1,k) { // dp转移 dp[u][i]+=dp[v][i-1], fs[u][i]+=fs[v][i-1]; } dp[u][1]+=dp[v][k], fs[u][1]+=fs[v][k]+dp[v][k]; } } int main() { scanf("%d %d", &n, &k); rep(i,1,n-1) { scanf("%d %d", &a, &b); G[a].push_back(b); G[b].push_back(a); } dfs(1, 0); printf("%lld ", ans); return 0; }