[P1351 NOIP2014 提高组] 联合权值

~~（挺水的题~~

首先这道题分成了两问：最大值和权值和

我们考虑在求的时候可以转化一下

反正是距离为二，那么说明有一个地方是被当成了中转站的

那么我们就可以枚举一下中转站，然后枚举一下出边

至于权值和，在枚举中转站的时候我们可以发现：

我们把所有的出边所对应的点的值拿出来放在一个序列里排个序，就相当于是求一遍两两乘积和

那么： $\sum_{1\le i,j\le n}a[i]*a[j]=(\sum_{i=1}^{n}a[i])^2-\sum_{i=1}^{n}a[i]^2$

因为几个数的和的平方就等于他们随便选出两个数相乘，然后我们只要减去重复选的就可以了

[P2515 HAOI2010]软件安装

这个题还是比较板子的题的，但是确实做了很长的时间（真…难调

首先我们观察一下题目：

每一个点都有且仅有一个父亲，但是……会出现一个叫做环的东西

那么我们把每一个点向自己的儿子连边的话，就可以找到这个环，并且一个联通图里最多只会有一个环

那么我们这个图是什么呢？显然就是一个基环树森林了啊

那么我们会发现如果有环的话，我们一整个环都是要选的

就用tarjan缩个点，然后跑一下普通的树形背包就可以了

（所以要不是因为套了个tarjan这就是个大水题

[P2279 HNOI2003]消防局的设立

这个题有两种做法，一种是树形dp一种是贪心，贪心比较简单就不写了

首先我们会发现，一个点他如果被选了，最多影响到的是五层点

那么一个点如果被影响，那他会怎么样呢，也一定是被自己的五层点所影响

那么我们设出dp函数 $f[i][0/1/2/3/4]$ 从这个点开始，他自己的父亲和爷爷都要被涉及到，父亲要被涉及到，自己要会被涉及到，自己子树下一层要涉及到，下两层要被涉及到的方案数

那么方程就可以很简单~~e xin~~的推出来：

$f[i][0]=\sum f[y][4]+1$ （下两层都会被我所影响

$f[i][1]=min(f[y][0]+\sum_{z!=y}f[z][3])$ 自己影响爷爷，别的都可以不影响爷爷

$f[i][2]=min(f[y][1]+\sum_{z!=y}f[z][2]$ 一个儿子到自己就可以了

$f[i][3]=\sum f[y][2]$

$f[i][4]=\sum f[y][3]$

没了

CF685B Kay and Snowflake

首先就是重心是有一个性质的：如果两棵树拼起来了之后，他们的整个树的重心实在两颗树的重心的连线上的

那么这样就好办了

我们对于每一颗子树来说都求出来它的重儿子，就是子树siz最大的儿子

如果说子树的siz最大不超过当前树的1/2就说明当前节点就是重心，否则就一直从儿子的重心一直向爹爹跳，一直跳到符合条件为止

[P4362 NOI2002] 贪吃的九头龙

这个题挺好的

这个题其实对于答案有贡献的其实只有染上了1号颜色的节点

如果说m是2的话，那么我们相邻的两个节点需要特判一下下

如果不是2的话，就不需要在dp的时候特判了

那么我们用经典的套路来说嘛：设 $f[i][j][0/1]$ 为i号节点，当前节点是不是1号节点

然后dp方程就可以显然的出来了：

$f[u][j][0]=min(f[u][j][0],min(f[v][t][0]+f[u][j-t][0]+(M==2)*e[i].w,f[v][t][1]+f[u][j-t][0])) f[u][j][1]=min(f[u][j][1],min(f[v][t][1]+f[u][j-t][1]+e[i].w,f[v][t][0]+f[u][j-t][1]))$

但是这样其实并不能过去。。。（样例都不行

我们发现f数组是会随时更新的，所以说我们要随时存一个数组

[P3177 HAOI2015] 树上染色

经典题 ——R

首先我们会发现，这个题猛然一想，应该是树形dp一样的东西，那么我们就可以考虑一下每一颗子树里的东西

如果我们在一棵子树中有x个黑点的话，字数外边就会有m-k个黑点，那么这些黑点之间的距离就会经过当前子树和父亲之间的连边，那么我们可以想到经典套路：路径拆边，把统计路径长度和变成统计每一条边被经过的次数，那根据上面的套路来说呢，我们就可以用树形dp统计每一条边经过的次数，就可以求出来了

[P2585 ZJOI2006]三色二叉树

哇，大经典题目了属于是

我们当然还是考虑树形dp

对于一个节点来说，如果它有一个子节点的话，子节点的颜色是不可以和他自己一样的，那么就说明了我们当前节点为绿色的方案数就是子节点不是绿色的方案数，两个子节点的话，就需要考虑一下三个节点都不一样了（这个是需要注意的）（强调）

那么我们其实只要记录一下一个节点是不是被染成了绿色，统计一下最多的绿色节点的个数就可以了

[P3047 USACO12FEB]Nearby Cows G

我们可以很显然的看出这个题似乎要用树形dp来做。。。但是猛然一看并没有什么思路

我们考虑在做这个题的时候是可以考虑，如果说我从根节点向下找的方法是很简单的，dfs一遍就可以

但是在考虑通过根节点的两端或者任何一个别的根节点的两端的时候，就可以用二次扫描

我们考虑当前点距离为k-2的话就相当于是和根节点距离为k-1的并且不经过我当前的点

[P3698 CQOI2017]小Q的棋盘

经典题了属于是

这个题就是说我们从根节点开始走n步可以走过多少点

那么我们考虑，从一个点开始来说，他只有几种情况：

走到自己的子树之后回来
走到自己的子树之后不回来
走到自己的一个子树之后回来再走到另一个子树里不回来

那么就很简单咯

（方程中有-1 -2 的操作是因为从子树中回到根节点是需要代价的

[P5658 CSP-S2019] 括号树

我们dfs的时候，就把左括号放到栈里面，如果说我们有一个右括号了之后就相当于是可以配对了嘛，那我们就弹栈

如果说我们配了个队之后我们会发现一件事情就是如果以配对的右括号为字串的右端点的话，我们不仅仅是可以拓展出一个答案的而是很多很多

所以我们要把左括号前面的一个右括号的答案加上

最后dfs的时候是要回溯的，弹栈进栈我就不说了。

[P2607 ZJOI2008] 骑士

这个题是不错的，基环树+没有上司的舞会

我们考虑这么一件事情：如果有n个点，n条边并且不保证联通的话这回是什么呢。。。

基环树森林

但是显然我们一看这道题就是没有上司的舞会

但是有基环树，就很。。。

但是基环树嘛。。。最多只有一个环

那么说明我们可以破环：在环上找到一个点，破掉他，然后跑一遍dp

但是破掉的边的断点是不可以都选的所以要特判一下

并且因为我们是一个环，相邻的两个点绝对不会都选上的，所以只需要破环一次（非常妙

[P4516 JSOI2018] 潜入行动

简化版题意：一个点如果被选中了的话就可以支配它所连接的所有点，但是不能支配自己，n个点中选出k个点使得可以支配一整棵树的方案数

首先上来先是一个思路： $f_{i,j,0/1}$ 表示i这个点选了j个点的方案数（选不选这个点

然后我们会发现这就是个背包。。。

才不是！

怎么可能这么简单

我们会发现一件事情就是，如果说我们当前的这个点已经被支配了，那么它的父亲可以不选，如果没有被支配，父亲是必选的

所以我们要额外记录一维来记录这个点有没有被支配

剩下的就是转移方程了…自己推去（大不了看代码去