考虑没有边权和限制时怎么做。

设 $f_{x,i}$ 表示点 $x$ 上连了 $\le i$ 条边时，$x$ 的子树中最多能被选择的边数。儿子转移到父亲时考虑此边是否选择即可：

$$f_{x,i}=\max_{y\in son_x}(f_{x,i}+f_{y,k},f_{x,i-1}+f_{y,k-1}+1)$$

考虑加入边权和的限制。当一条边 $x\rightarrow y$ 被选择时，此边会给总边权和带来 $w_{x,y}$ 的贡献。那么用 $f_{x,i}$ 记录一个二元组 $(a,b)$ 表示答案。

定义广义加法：

$$(a,b)+(c,d)=(a+c,b+d)$$

定义广义 $\max$：

$$\max((a,b),(c,d))=\begin{cases} (a,\min(b,d))&\text{if }a=c\\ (a,b)&\text{if }a>c\\ (c,d)&\text{if }a<c \end{cases}$$

转移：

$$f_{x,i}=\max_{y\in son_x}(f_{x,i}+f_{y,k},f_{x,i-1}+f_{y,k-1}+(1,w_{x,y}))$$

这样就足以通过本题。但空间上还可以继续优化。观察转移，发现只有 $f_{y,k-1},f_{y,k}$ 被用到，考虑把状态改为 $f_{x,0/1}$ 表示点 $x$ 上连了 $k-1/k$ 条边时，$x$ 的子树的答案。同时再记一个临时数组 $F_{i}$ 表示当前点 $x$ 的 $f_{x,i}$。

转移就可以变为：

$$F_{i}=\max_{y\in son_x}(F_{i}+f_{y,1},F_{i-1}+f_{y,0}+(1,w_{x,y}))$$

转移完后记得把 $F_{k-1},F_{k}$ 赋值给 $f_{x,0/1}$。

#include <bits/stdc++.h>
#define LL long long
#define PII pair <int, int>
using namespace std;
const int maxn = 1e5 + 10;
int n, k, fa[maxn], w[maxn];
vector <PII> G[maxn];
struct info {
	LL siz, sum;
	friend info operator + (info x, info y) {
		return {x.siz + y.siz, x.sum + y.sum};
	}
}f[maxn][2], F[110];
info max(info x, info y) {
	if(x.siz == y.siz) return {x.siz, min(x.sum, y.sum)};
	else if(x.siz > y.siz) return x;
	else return y;
}
void dfs(int x) {
	for(auto tmp : G[x]) {
		int y = tmp.first, z = tmp.second;
		dfs(y);
	}
	for(int i = 0; i <= k; i++) F[i] = {0, 0};
	for(auto tmp : G[x]) {
		int y = tmp.first, z = tmp.second;
		for(int i = k; i >= 0; i--) {
			F[i] = F[i] + f[y][1];
			if(i >= 1) F[i] = max(F[i], F[i - 1] + f[y][0] + (info){1, z});
		}
	}
	f[x][0] = F[k - 1], f[x][1] = F[k];
}
int main() {
	scanf("%d%d", &n, &k);
	for(int i = 2; i <= n; i++) {
		scanf("%d%d", &fa[i], &w[i]);
		G[fa[i]].push_back({i, w[i]});
	}
	dfs(1);
	printf("%lld %lld\n", f[1][1].siz, f[1][1].sum);
	return 0;
}