洛谷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;
}