POI2014 洛谷P3574 FarmCraft 题解

题目链接

https://www.luogu.com.cn/problem/P3574

题目大意

给定一棵树，每个结点有一个村庄，小明从 \(1\) 号结点出发，每条边仅往返各一次，他每次到达一个村庄，就放下一台电脑，并立即向其他村庄行进。小明走每条边需要花费一个单位时间。每个村庄收到电脑后，会立即安装一款软件，第 \(i\) 个村庄安装软件需要花费 \(c[i]\) 的时间。小明最终返回 \(1\) 号结点后，才会给自己安装软件。问所有村庄都安装完软件最少需要多长时间。

输入格式

一个 \(n\)，表示结点个数；
\(n\) 个数，表示每个结点安装软件需要花费的时间
\(n-1\) 行，每行两个数，表示每条边

输出格式

就是最少时间

输入样例

6
1 8 9 6 3 2
1 3
2 3
3 4
4 5
4 6

输出样例

分析

我们考虑这个题目的答案的构成。需要最少的时间，一部分是他走完所有村庄的时间的开销 \(+\) 他自己安装软件；
另一部分是返回到 \(1\) 号结点后等待其他村庄安装完成的时间，两者取最大值即可。
对于后者来说，我们必须先求出返回每棵子树的根结点后，还需要等待的时间，才能退出最终结果。
因此，我们尅定义 \(f[i]\) 表示返回以 \(i\) 为根的子树的根结点 \(i\)，要完成安装，还需要等待的时间。

对于以 \(i(i>1)\) 号结点为根的子树，从 \(i\) 出发走完并返回 \(i\) 所需要的时间为 \(2\times (size[i]-1)\)，其中\(size[i]\) 表示子树 \(i\) 总共的结点个数。
那么只考虑自己安装软件的情况下，需要等待的时间为 \(a[i]-2\times(size[i]-1)\)，如果小于 \(0\)，说明返回后软件已经安装完成，所以对结果的真正的贡献为 \(\max(0, a[i]-2\times(size[i]-1))\)
当然可能他的子孙结点的安装软件速度很慢，有可能大于上述的贡献值，因此我们还要考虑子结点的贡献。
由于 \(i\) 每个孩子结点都会有一个等待时间，因此我们在走的时候，优先走等待时间长的，把等待的时间消耗在遍历其他孩子的路上，这样才能使得结果最优，证明还没想好，稍后附上……
我们在求得每个孩子 \(son[j]\) 的最少等待时间后，按照等待时间将序排列，依次更新父结点的等待时间，递推式如下：
假设在处理孩子 \(son[j]\) 之前，需要等待的时间为 \(f[i]\)，此时再来一个孩子 \(son[j]\)，那么等待时间需要更新为 \(\max(f[i]-size[son[j]], f[son[j]]-1, 0)\)，即原来的等待时间减去遍历 \(son[j]\) 消耗的时间，与 \(son[j]\) 提供的等待时间（减 \(1\) 是要从孩子结点回到父结点）的最大值，同时，这里面也包含了上面“只考虑自己安装软件”的情况。
因此，我们综合一下上面的式子：
- 起初刚到 \(i\) 的时候，要安装软件，所以 \(f[i] = a[i]\)
- \(f[i]=max(f[i]-size[son[j]], f[son[j]]-1, 0)\)，其中第一项为 \(i\) 自身安装的贡献，第二项为 \(son[j]\) 的贡献，第三项理所当然最少的等待时间为 \(0\)。
最终的答案特殊处理一下，因为 \(1\) 号结点最后安装，所以\(ans=\max(a[1], f[1])+2\times (size[1]-1)\)
注意，这里的 \(a[1]\) 最开始改成了 \(0\)，因为开始 \(1\) 不安装，最后求解的时候再将 \(a[1]\) 改回原值

部分代码

void dfs(int now, int fa) { // 返回i为根的子树，所有都安装完最小等待时间
	vector vet;
	size[now] = 1;
	f[now] = a[now];
	for (int i = head[now]; i; i = e[i].next) {
		int to = e[i].to;
		if (to == fa) continue;
		dfs(to, now);
		size[now] += size[to];
		vet.push_back(Node(to, f[to]));
	}
	sort(vet.begin(), vet.end()); // 对孩子的等待时间降序排列
	for (int i = 0; i < vet.size(); ++i) {
		int son = vet[i].id;
		// f[son]-1表示son返回父结点后还需要等待的时间
		// f[now]-(size[son]<<1)表示从now跑完son这棵子树返回后还需要等待的时间
		f[now] = max(max(f[son]-1, (ll)0), f[now]-(size[son]<<1));
	}
}

// 最后的答案，x 为原来 1 安装的耗时
printf("%lld", max(f[1], (ll)x)+(size[1]-1<<1));

树型Dp