Summary

　　今天放假，比赛于是就没有打了，但是看了一下题，发现都挺简单了，不想码~╮(╯▽╰)╭懒虫一条。最后一题居然做过原题。这次比赛让我对并查集“刮目相看”，对贪心感到“前途无量”，觉得树形DP很有趣，但也很难，但也都打出来了。要多做关于树形DP的题目，来充实自己。

Problem

T1 【GDOI2003】购物

题目大意

　　给你很多种物品，你购买每个物品就可以剩下a_i钱，但是编号x和y号物品，买了其一，就不能买其二，且不会出现一个环的情况。问最多能节省多少钱。

想法

　　这道题好像做过一道类似的题目，是“没有上司的舞会”，是我第一道树形DP的题目

　　方法有两种，两种都可以说一下：

（1）树形DP

　　分为两种情况，一种是没有限制的点，一种是有限制的点

　　①有限制的点

　　对于这一类点，我们可以把他们一串一串的连成一棵树，使之成为森林，然后，我们对于每一棵树进行树形DP，看看每一棵树，最多可以节省多少钱。

　　设f[i,0/1]表示选不选编号为i的点

　　如果选，那么它的儿子就不可以选，也可以说它的父亲不可以选，但是，我们在判断的父亲选时，那它就不能选了，所以我们只需要判断它的儿子不能选即可。

　　f[i,1]:=∑f[j,0]（j为i的儿子），它的儿子只能不选，那么就看看不选时，每个儿子的最大值，求和即可

　　如果不选，那么它的儿子可以选或者不选，我们就判断一下它的儿子选还是不选，分两种情况讨论

　　f[i,0]:=∑max(f[j,0],f[j,1])（j为i的儿子）

　　套上树形DP千年不变的递归模型，求解就行了

　　②无限制的点

　　这类点直接加上他可以节省的钱数就可以了

（2）二分图+网络流

　　听大神们说，树形DP打多了，试试新口味

　　我也想打，但是，树（网）形（络）D（流）P（不）没（会）打（打）腻（啊）

T2 blockenemy

题目大意

　　给一个树，有些节点上有敌人，树边存在权值，先要删除若干条边，使得敌人各不相连的最小代价是多少？

想法

　　这道题是一道很好的树形DP练手题目，同时也可以用并查集+贪心来做，现在讲一下两种做法

（1）树形DP

　　设f[x]表示以x为根，它子树的敌人都不可以互相联络，且无法到达点x的最小价值

　　设g[x]表示以x为根，它子树的敌人都不可以互相联络，但是其中一个敌人可以到达x这个点的最小价值

　　这个状态设得异常巧妙，在我看过这道题的所有题解，这是最好理解的

　　其实，解题的关键，就是状态和转移上面了！

　　我们考虑两种情况，如果当前x上有敌人，或者没有敌人，应该怎么做。

　　①有敌人

　　如果有敌人，那么f[x]就赋值为无穷大，因为他根本不可以“无法到达点x”

　　这时，我们考虑g[x]给之后的转移用，到底g[x]应该是多少

　　显然是g[x]=∑min(f[y],g[y]+dis[x,y])，（y是x的儿子）为什么呢？

　　因为x这个点有敌人了，那么g[x]本身就符合条件了

　　因为f[y]的时候，没有点可以互相联络，如果多添一个点x，那么他就是g[x]的条件了，所以它是取最小值的两个数之一

　　因为g[y]已经符合条件了，如果多添一个点x，那么他就不符合g[x]的条件了，因为他有2个点可以到达x，所以我们需要x~y之间连一条边，保证只有1个点可以到达x

　   ②无敌人

　　f[x]=∑min(f[y],g[y]+dis[x,y])（y是x的儿子）为什么呢？

　　跟上面g数组的转移差不多

　　f[y]是符合条件的，所以多添一个点还是fx的条件，所以是取最小值的两个数之一、

　　g[y]是不符合条件的，他有1个点可以到达x，所以x~y之间连一条边，保证没有点可以到达x

　　可是，这时，g[x]怎么做的？怎么转移是本题解题的关键所在

　　g[x]一定是在f[x]的基础上转移的！使得它的某个儿子不可以到达x

　　对于每个儿子y，我们要将它的贡献值min(g[y]+dis[x,y],f[y])变成f[y]

　　如果这么做，g[x]:=f[x]-(min(g[y]+dis[x,y],f[y])-g[y])

2017.07.09【NOIP提高组】模拟赛B组