[长链剖分+DP]Codeforces1009F【Dominant Indices】题解
题目概述CF1009F解题报告定义 $f_{i,j}$ 表示 $i$ 子树内到 $i$ 距离为 $j$ 的个数，则显然 $f_{i,0}=1,f_{i,j}=\sum_{u\in son(i)}...
[贪心+树形DP]LOJ6042(雅礼集训 2017 Day7)【跳蚤王国的宰相】题解
题目概述给出一棵 $n$ 个节点的树，求每个点成为与其他点距离和最小点最少需要删除并加上的边数 $k$（新加边之后依然是一棵树）。解题报告我根本发现不了性质.jpg。可以证明，到其他点距离和最小...
[树形DP]liu_runda NOIP模拟题【蚊子】题解
解题报告这题在现在看来好像不是很难啊……把每对蚊子分开考虑，那么就是考虑每个节点作为LCA时的贡献，而每个节点作为LCA时又可以拆成两半处理，这样问题就简化得比较好处理了。一个叶子到达某个祖先没...
[树形DP]入门BZOJ3004(Noi2016十连测第一场)【访问计划】题解
题目概述有一棵带边权的树，现在要从根节点出发，至少经过所有边一次，可以传送 $K$ 次，代价为 $C$ 。问走回根节点经过的最小边权和。解题报告先考虑把传送换成另一个问题，经过一条路径并走回来的...
[树形DP]LOJ2485(CEOI2017)【Chase】题解
题目概述有 $n$ 个点的树，每个点上有 $p_i$ 只咕咕咕。从任意点出发开始走，有 $k$ 次放面包的机会，放下面包后相邻点的咕咕咕就会凑到该点，问先走一遍之后再走一遍遇到的咕咕咕个数之差最...
[分数规划+树形DP]BZOJ4753(Jsoi2016)【最佳团体】题解
题目概述有 $n+1$ 个人，选第 $i$ 个人需要花费 $s_i$ ，得到 $p_i$ 的贡献，第一个人必选，没有花费和贡献。$2\sim n+1$ 都有一个推荐人（推荐人编号小于自己的编号）...
[树形背包+复杂度分析]LOJ2124(HAOI2015)【树上染色】题解
题目概述有一棵点数为 $n$ 的树，树边有边权。给你一个正整数 $K$ ，你要在这棵树中选择 $K$ 个点，将其染成黑色，并将其他的 $n−K$ 个点染成白色。将所有点染色后，你会获得黑点两两之...
[树形DP+two-pointer]2016计蒜之道初赛第六场【微软的员工福利】题解
题目概述有 $n$ 个ZZK给JZ打工，他们的上下级关系是一棵树。现在JZ要给蒟蒻ZZK输送一定的神犇之力，每个ZZK可以得到 $r_i$ 点神犇之力或者 $p_i$ 点神犇之力。但是在ZZK得...
