题目大意

给定一颗以1为根节点的树，每个节点有一个购入价格p和卖出价格q。

进入一个节点时需要花费p，离开时可以收回q，每个节点只产生一次购入和卖出。

请你选择一个遍历的顺序，要求在遍历的过程中身上的钱数不小于0，且出发时带的钱数最少。

按照遍历的顺序是指：当你选择了一颗子树之后，你需要将这个子树全部走完，才能选择其他子树。

解题思路

该题为一道树形图上的贪心问题。

我们每一步的决策在于：当遍历到一个根时，对于其拥有的若干颗子树，应该以怎样的顺序来遍历这些子树。

先将问题简化为二叉树，并且两颗子树都只有根节点：

首先我们选择左边的路径，则需要携带的钱数为：

经过1: L1 = p1

经过2: L2 = p1-q1+p2

经过3: L3 = p1-q1+p2-q2+p3

然后考虑走右边的情况：

经过1: R1 = p1

经过3: R2 = p1-q1+p3

经过2: R3 = p1-q1+p3-q3+p2

对于这6个值，我们要求的是min( max(L1, L2, L3), max(R1, R2, R3) )

由于在题目中已经明确说明总是有p≥q，可以肯定有L3≥R2,R3≥L2，所以可以直接将L2和R2排除。

又因为1是必经之路，因此在选择左右时，实际上需要比较的只有L3和R3。

我们将L3和R3换一种形式表示：pSum = p1+p2+p3, qSum = q1+q2+q3，则L3=pSum-qSum+q3,R3=pSum-qSum+q2

若L3>R3，则有q3>q2，此时要选择的是R3，即走右路；

若L3<R3，则有q2>q3，此时要选择的是L3，即走左路。

由于pSum和qSum的值是确定的，因此实际上我们只需要根据q2和q3的值就可以选择走哪边。

最后的结论也就是：对于二叉树的情况，我们选择q值大的一边先走，一定能保证结果值最小

那么接下来将这个结论推广至多叉树的情况：

对于多叉树的情况，我们将子树按照q值从大到小的顺序，一定能保证结果值最小

这是由于q值之间的大小顺序是绝对的，假设3个子节点分别为A,B,C，若qA≥qB,qB≥qC，则一定有qA≥qC。

不妨举个例子：

根据q值，对应的6种遍历顺序分别为：

1,2,3：需要带钱8 1,3,2：需要带钱7 2,1,3：需要带钱8 2,3,1：需要带钱7 3,1,2：需要带钱7 3,2,1：需要带钱6

那么还有一个问题，一个节点的p和q是直接给定的，我们应该如何来求一颗子树的pt和qt（为了便于区分，我们将树的p和q记为pt和qt）？

在计算过程中，我们采用递归的从根节点开始遍历。在计算当前节点时，我们需要将其子树的p和q都先计算出来。

因此在计算当前子树时，我们已经知道了根节点的p和q，以及每颗子树的pt和qt（记作pt1,pt2,pt3,...和qt1,qt2,qt3,...，并且满足qt1≥qt2≥qt3≥...）。

在该题中所有节点的总购买钱数不会超过200,000,000，不妨设置一个初始钱数wallet = 200000000。

同时我们还需要一个值minWallet，来记录钱包钱数最少时的值，初始也为200,000,000。

首先处理根节点：

wallet = wallet - p If (minWallet > wallet) ThenminWallet = wallet End If wallet = wallet + q

接下来处理每个子树：

For i = 1 .. chdNumberwallet = wallet - pt[i]If (minWallet > wallet) ThenminWallet = walletEnd Ifwallet = wallet + qt[i] End For

最后可以得到整个树的p和q分别为：

pt[root] = 200000000 - minWallet // 遍历这颗树至少需要的钱数 qt[root] = wallet - minWallet // 最后的钱数-花费的钱数=返还的钱数

完整的伪代码为：

DFS(rt):wallet = 200000000minWallet = 200000000// 先递归处理每个子树For each child i of rtDFS(i)End For// 对该根节点的所有子树按照qt值排序sortByQt(children)// 处理根节点wallet = wallet - p[rt]If (minWallet > wallet) ThenminWallet = walletEnd Ifwallet = wallet + q[rt]// 处理子树For each child i of rtwallet = wallet - pt[i]If (minWallet > wallet) ThenminWallet = walletEnd Ifwallet = wallet + qt[i]End For// 记录子树pt[rt] = 200000000 - minWalletqt[rt] = wallet - minWallet

最后所求的结果是pt[1]。

由于在每一颗子树都使用了排序，最后这个算法的时间复杂度为O(NlogN)，即使在N为10000的数据下，也能够顺理通过。

#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std;const int maxn = 10005; const int inf = 200000000; struct Node {vector<int> child; }tree[maxn]; int n,p[maxn],q[maxn]; int pt[maxn],qt[maxn];bool cmp(int a,int b) {return qt[a] > qt[b]; }void dfs(int u,int fa) {int Wallet = inf;int minWallet = inf;vector<int> V = tree[u].child;for(int i = 0; i < V.size(); i++){int v = V[i];if(v == fa) continue;dfs(v,u);}sort(V.begin(),V.end(),cmp);Wallet = Wallet - p[u];if(minWallet > Wallet)minWallet = Wallet;Wallet = Wallet + q[u];for(int i = 0; i < V.size(); i++){if(V[i] == fa) continue;Wallet = Wallet - pt[V[i]];if(minWallet > Wallet)minWallet = Wallet;Wallet = Wallet + qt[V[i]];}pt[u] = inf - minWallet;qt[u] = Wallet - minWallet; }int main() {int u,v;while(scanf("%d",&n)!=EOF){for(int i = 1; i <= n; i++)scanf("%d%d",&p[i],&q[i]);for(int i = 1; i <= n; i++) tree[i].child.clear();for(int i = 1; i < n; i++){scanf("%d%d",&u,&v);tree[u].child.push_back(v);tree[v].child.push_back(u);}dfs(1,0);printf("%d\n",pt[1]);}return 0; }

总结

以上是生活随笔为你收集整理的hihocoder Tower Defense Game(树上贪心)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。