前言

学校模拟赛场切失败故写题解留念。

正文

一道卡卡空间的树上背包题。

树上背包状态为 $f_{i,~j,~k}$，意为以 $i$ 为根的子树进行了 $j$ 次漂流后最远距离本点 $k-1$ 距离的点的代价，特别的，$f_{i,~j,~0}$ 为以 $i$ 为根的子树进行了 $j$ 次漂流后全部被照亮的代价。

我们转移以 $i$ 为根时的状态时暂不考虑 $k=0$ 的状态，先将 $k$ 整体降低一层进行转移，计算出所有 $f'_{i,~j,~k}=f_{i,~j,~k+1}$，第 $i$ 个点对于每个儿子 $v$ 状态转移如下：

$$f'_{i,~j+\_j,~k}=\min_{k_1=0}^{k}f'_{i,~j,~k_1}+\min_{k_2=0}^kf_{v,~\_j,~k_2}$$

然后考虑怎样转移 $f_{i,~j,~0}$。

我们让所有 $a_i=\min a_v$，这里 $v$ 表示以 $i$ 为根地子树中的所有可能地点，显然这样是优的。

我们知道对于一个点而言，这个点最优的转移策略为被他自己或他的直系的所有父亲照亮，如果有更远地点想照亮这个点，总会重新又归位到两点的最近公共祖先上，所以我们反着考虑，想要照亮所有儿子以及自己，一定是让自己发光到刚好照亮所有儿子。

由于一个点的子树中使用漂流也会导致这个点亮度增加，所以实际当前点本身的亮度是额外单独使用 $a_i$ 的次数与子树中已经使用的漂流之和.

所以状态转移方程如下：

$$f_{i,~k,~0}=min_{j=0}^{siz_i}f_{i,~j,~k}+a_i\times \max(0,~k-j)$$

其中 $siz_i$ 为以 $i$ 为根的子树的大小（应该没有人写树上背包不带 $siz$ 的吧）。

初始化的话 $f$ 直接全部赋值成极大值，最终答案为 $min_{i=1}^nf_{1,~i,~0}$。

由于这样写时间和空间都会是 $\Theta(n^3)$，空间无法承受 $700\times700\times700\times8=2744000000B\approx 2.56GB$，所以要随用随毁，通过返回一个二维 $vector$ 的方式精细实现。

代码

#include <cstdio>
#include <cstring>
#include <vector>
#define ll unsigned long long
#define ui unsigned short
#define N 702
#define INF 0x3f3f3f3f3f3f3f3f
ll min(const ll a, const ll b) {
	return a < b ? a : b;
}
ll max(const ll a, const ll b) {
	return a > b ? a : b;
}
template<typename T> void read(T& x) {
	x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		ch = getchar();
	while (ch >= '0' && ch <= '9')
		x = (x << 3) + (x << 1) + (ch & 15), ch = getchar();
}
template<typename T> void write(T x) {
	if (x == 0) {
		putchar('0');
		return ;
	}
	ui a[25], t = 0;
	while (x)
		a[++t] = x % 10, x /= 10;
	while (t)
		putchar(a[t--] | 48);
}

struct Edge {
	ui to, nxt;
} edge[N];
ui n, fa, head[N], idx, siz[N];
ll a[N], ans, t[N][N];

void add(const ui u, const ui v) {
	edge[++idx].to = v, edge[idx].nxt = head[u], head[u] = idx;
}

std :: vector<std :: vector<ll> > dfs(const ui u) {
	std :: vector<std :: vector<ll> > f;
	for (ui i = 0; i <= siz[u]; ++i)
		f.push_back(std :: vector<ll> (siz[u] + 1, INF));
	siz[u] = 1, f[0][0] = 0;
	for (ui i = head[u]; i; i = edge[i].nxt) {
		const ui v = edge[i].to;
		const std :: vector<std :: vector<ll> > g = dfs(v);
		const ui sz = siz[u] + siz[v];
		ui j = 0, _j, k;
		ll minn, min2;
		for (; j <= siz[u]; ++j)
			for (_j = 0; _j <= siz[v]; ++_j)
				for (minn = f[j][k = 0], min2 = g[_j][0]; k <= sz; minn = min(minn, f[j][++k]), (k <= siz[v] && (min2 = min(min2, g[_j][k]))))
					t[j + _j][k] = min(t[j + _j][k], minn + min2);
		siz[u] = sz;
		for (ui j = 0; j <= sz; ++j)
			for (ui k = 0; k <= sz; ++k)
				f[j][k] = t[j][k], t[j][k] = INF;
	}
	for (ui i = 0; i <= siz[u]; f[i++][0] = INF)
		for (ui j = siz[u]; j; --j)
			f[i][j] = f[i][j - 1];
	for (ui i = 0; i <= siz[u]; ++i)
		for (ui j = 0; j <= siz[u]; ++j)
			f[i][0] = min(f[i][0], f[j][i] + (i > j ? i - j : 0) * a[u]);
	return f;
}

int main() {
	memset(t, 0x3f, sizeof t);
	read(n);
	for (ui i = 2; i <= n; ++i) {
		read(fa);
		add(fa, i);
	}
	for (ui i = 1; i <= n; ++i)
		read(a[i]);
	for (ui u = n; u; ++siz[u--])
		for (ui i = head[u]; i; i = edge[i].nxt)
			a[u] = min(a[u], a[edge[i].to]), siz[u] += siz[edge[i].to];
	const std :: vector<std :: vector<ll> > f = dfs(1);
	ans = f[n][0];
	for (ui i = 1; i < n; ++i)
		ans = min(ans, f[i][0]);
	write(ans);
	return 0;
}