2020ICPC南京 M.Monster Hunter

题目大意

一颗根为 \(1\) 的有 \(??(2≤??≤2000)\) 个节点的树，每个节点有一个权值 \(???_{??} (1≤???_{??}≤10^9)\) ，能删除某个点的前提是其父亲节点已经被删除，并且删除一个节点的费用为 \(???_{??}+∑_{??∈??????[??]}???_{??}\) ，有 \(??\) 次使用魔法的机会，每次使用可以免费并且无视限制条件地删去 \(1\) 个节点。分别求出当 \(??=0\sim ??\) 时，删除全部节点所需要的最小花费。

思路

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#pragma warning(disable :4996)
const double eps = 1e-8;
const LL mod = 1000000007;
const LL MOD = 998244353;
const int maxn = 2010;

int T, N;
vectorG[maxn];
int vsize[maxn];
int hp[maxn], dp[maxn][maxn][2];

void add_edge(int from, int to)
{
	G[from].push_back(to);
}

void dfs(int v)
{
	vsize[v] = 1;
	dp[v][0][0] = hp[v], dp[v][1][1] = 0;
	for (int i = 0; i < G[v].size(); i++)
	{
		int to = G[v][i];
		dfs(to);
		for (int j = vsize[v]; j >= 0; j--)
		{
			for (int k = vsize[to]; k >= 1; k--)
			{
				if (j < vsize[v])
					dp[v][j + k][0] = min(dp[v][j + k][0], dp[v][j][0] + min(dp[to][k][0] + hp[to], dp[to][k][1]));
				if (j > 0)
					dp[v][j + k][1] = min(dp[v][j + k][1], dp[v][j][1] + min(dp[to][k][0], dp[to][k][1]));
			}
			dp[v][j][0] += min(dp[to][0][0] + hp[to], dp[to][0][1]);
			dp[v][j][1] += min(dp[to][0][0], dp[to][0][1]);
		}
		vsize[v] += vsize[to];
	}
}

void solve()
{
	dfs(1);
	for (int i = 0; i <= N; i++)
	{
		if (i < N)
			printf("%lld ", min(dp[1][i][0], dp[1][i][1]));
		else
			printf("%lld\n", min(dp[1][i][0], dp[1][i][1]));
	}
}

signed main()
{
	scanf("%lld", &T);
	while (T--)
	{
		//cnt = 0;
		scanf("%lld", &N);
		for (int i = 0; i <= N; i++)
		{
			for (int j = 0; j <= N; j++)
				dp[i][j][0] = dp[i][j][1] = INF;
		}
		for (int i = 1; i <= N; i++)
			G[i].clear();
		int fa;
		for (int i = 2; i <= N; i++)
		{
			scanf("%lld", &fa);
			add_edge(fa, i);
		}
		for (int i = 1; i <= N; i++)
			scanf("%lld", &hp[i]);
		solve();
	}

	return 0;
}