Summary
今天放假，比赛于是就没有打了，但是看了一下题，发现都挺简单了，不想码~╮(╯▽╰)╭懒虫一条。最后一题居然做过原题。这次比赛让我对并查集“刮目相看”，对贪心感到“前途无量”，觉得树形DP很有趣，但也很难，但也都打出来了。要多做关于树形DP的题目，来充实自己。
Problem
T1 【GDOI2003】购物
题目大意
给你很多种物品，你购买每个物品就可以剩下ai钱，但是编号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]的基础上转移的！使得它的某个儿子不可以到达
其实，就是把f[x]中，一个花费最大的一次删除敌人到x的边的价值，删掉
重点
上面说了f[x]=min(f[y],g[y]+dis[x,y])(其中一个)，我们把可以到达x这个点，变成不可以到达这个点，然后就有两种情况
一种就是g[y]+dis，如下图
试想一下，原本y点为根的子树是可以到达y的，但是删去了x~y之间的边就不可以到达了，也就是说，是从未知点~x~y的，是这样的顺序
还有一种情况就是f[y]，同上图
就是原本的
我们由min(g[y]+dis,f[y])变成g[y]就是上面所说
f[x]就会在f[x]的基础上减去min(g[y]+ w, f[y]) – g[y]，那么这个值越大，f[x]就会越小。
f[x]-g[y]就是那个让原本可以到y的，变成不能到y的那条边，f[x]-这条边的最大值，就是g[x]
显然是取最大值，这样g[x]就变得很小
我发个连续的段子，结合图片和f,g数组的定义看，一定可以看得懂
“G[x]的转移有那么一丢丢难想。G[x]一定实在f[x]的基础上，使得某个儿子从不能到达x，变成能到达x，即儿子y对该状态的贡献由min(g[y] + w, f[y])变为g[x].如果这样的话，f[x]就会在f[x]的基础上减去min(g[y]+ w, f[y]) – g[y]，那么这个值越大，f[x]就会越小。”
（2）贪心+并查集
思想跟最小生成树一样，简直一模一样
可以通过O(n^2)判断加多一条边是否可以符合题目条件
边从大到小选
如果n大一点，上面的判断可以改成O(m)的，m是边数，根据深度来搜索每一个点。
T3 treecut
题目大意
给一棵无根树，删掉某一个点，使得每个连通块节点个数不大于原来节点个数的一半，求这些点
想法
我们试着让每一个点都当作根做一遍，用快速的方法来求每个连通块的个数即可，十分简单。