洛谷P3354 [IOI2005]Riv 河流题解

题目链接：P3354 [IOI2005]Riv 河流

题意：

几乎整个 Byteland 王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫 Bytetown。

在 Byteland 国，有 $n$ 个伐木的村庄，这些村庄都座落在河边。目前在 Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到 Bytetown 的伐木场。Byteland 的国王决定，为了减少运输木料的费用，再额外地建造 $k$ 个伐木场。这 $k$ 个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到 Bytetown 了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。

注：所有的河流都不会分叉，形成一棵树，根结点是 Bytetown。

国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米 $1$ 分钱。

对于 $50\%$ 的数据，保证 $n\le 20$。

对于 $100\%$ 的数据，保证 $2\le n\le 100$，$1\le k\le \min(n,50)$，$0\le v_i\le n$，$0\le w_i\le 10^4$，$1\le d_i\le 10^4$。

保证每年所有的木料流到 bytetown 的运费不超过 $2\times 10^9$ 分。

~~题解区写的啥啊~~ 那我来一篇正经的树上背包吧

注意到经典的 $dp[u][j]$ 表示 $u$ 所在子树建了 $j$ 个伐木场的最小花费，是无法计算的，因为我们并不知道子树有多少木头，以及他们会运到哪里

考虑记录一下 $u$ 结点是否放伐木场，同时把最小花费转化为最大价值

怎么转化？对于一个结点，在它上面建伐木场，则从该结点向叶子结点走，

每次遇到的第一个伐木场之前的，都会将木材运至 $u$ ，而不是根节点

设 $f[u][j]$ 表示 $u$ 所在子树建了 $j$ 个伐木场，且 $u$ 不建伐木场的最大价值（也就是最多节省的路费）

设 $g[u][j]$ 表示 $u$ 所在子树建了 $j$ 个伐木场，且 $u$ 必须建伐木场的最大价值

那么对于每个结点，木头要上传（根节点方向）到哪个结点呢

一种写法是增加一维记录最近的祖先伐木场在哪里，然后用栈维护

注：我本来写的是上面的，但是复杂度有点高（虽然能过）

这里讲一种不用增加维度的方法

我们每次假定 $u$ 一定建伐木场，然后对于每个 $u$ 都求出它的 $f$ 数组

同时设一个 $h[u][j]= \max(f[u][j],g[u][j])$ ，

当然实际上我们不需要单独设数组，直接合并到 $f$ 里就行了

然后将 $f$ （也就是 $h$ ）转移到 $g$ 上，清空 $f$ 数组

重复这样的过程，然后根节点单独处理即可

时间复杂度 $O(n^2k)$ ，目前没卡常rank3（~~rank1是假的不管了~~）

~~好像官方题解是 $O(n^2k^2)$ 的，不过那都是多老的东西了~~

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
#define N (int)(115)
int n,m,ans,val[N],tmp[N];
int dis[N],sz[N],f[N][N],g[N][N];
struct Edge
{
	int u,v,w,next;
}e[N];
int pos=1,head[N];
void addEdge(int u,int v,int w)
{
	e[++pos]={u,v,w,head[u]};
	head[u]=pos;
}
void Max(int &a,int b){a=a>b?a:b;} 
void DP(int u,int gra)
{
	f[u][0]=dis[gra]*val[u];
	for(int i=head[u]; i; i=e[i].next)
	{
		int v=e[i].v; DP(v,gra);
		for(int j=0; j<=min(m,sz[u]); j++)
			tmp[j]=f[u][j];
		for(int j=0; j<=min(m,sz[u]); j++)
			for(int k=0; k<=min(m,sz[v])&&j+k<=m; k++)
				Max(f[u][j+k],tmp[j]+f[v][k]);
	}
	for(int j=1; j<=min(m,sz[u]); j++) Max(f[u][j],g[u][j]);
}
void dfs(int u)
{
	sz[u]=1;
	for(int i=head[u]; i; i=e[i].next)
	{
		int v=e[i].v;
		dis[v]=e[i].w+dis[u]; 
		dfs(v); 
	}
	g[u][0]=0; ans+=dis[u]*val[u];
	memset(f,0,sizeof(f));
	for(int i=head[u]; i; i=e[i].next)
	{
		int v=e[i].v; DP(v,u);
		for(int j=0; j<=min(m,sz[u]); j++)
			tmp[j]=g[u][j];
		for(int j=0; j<=min(m,sz[u]); j++)
			for(int k=0; k<=min(m,sz[v])&&j+k<=m; k++)
				Max(g[u][j+k],tmp[j]+f[v][k]);
		sz[u]+=sz[v];
	}
	for(int i=min(m,sz[u]); i>=1; i--)
		g[u][i]=g[u][i-1]+dis[u]*val[u]; // 强制u建别忘了
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=1,v,w; i<=n; i++)
	{
		cin >> val[i] >> v >> w;
		addEdge(v,i,w);
	}
	dfs(0);int res=0;
	memset(f,0,sizeof(f));sz[0]=1;
	for(int i=head[0]; i; i=e[i].next) 
	{
		int v=e[i].v; DP(v,0);
		for(int j=0; j<=min(m,sz[0]); j++)
			tmp[j]=f[0][j];
        for(int j=0; j<=min(m,sz[0]); j++)
			for(int k=0; k<=min(m,sz[v])&&j+k<=m; k++)
				Max(f[0][j+k],tmp[j]+f[v][k]);
		sz[0]+=sz[v];
	}
	for(int i=1; i<=min(m,sz[0]); i++) res=max(res,f[0][i]);
	cout << ans-res << '\n';
	return 0;
}