本周无

本周无

本周无

树上差分

本周无

本周无

本周无

本周无

林星涵：

题目大意：

数据范围：

解题思路：

推荐理由：

陶吟翔：

题目大意：

数据范围：

解题思路：

推荐理由：

郭衍培：

题目大意：给定n的点的树树，每个点有两个权值h,t。将所有边分成若干个集合，要求每个集合内的边构成一条路径，且路径上点的h不减。每个集合的代价为路径上所有点的t之和。求最小总代价。

数据范围：$n\le 2\times 10^5$,$1\le h,t\le 10^6$

解题思路：可以将树上的边看成有向的，由h较小的指向h较大的。每个点会被计算max{in,out}次，in，out分别表示点的入度和出度。但问题在于两端点h相同的边如何处理。先去掉已经确定方向的边，留下一个森林。对于剩下的每棵树，dp1[i]表示从i节点指向其父亲节点，i节点子树的最小代价，dp2[i]表示从i节点父亲指向i的最小代价。计算一个节点的dp值时，枚举子节点中指向它的个数。将子节点按照dp1-dp2排序，从小到大依次加入。

推荐理由：问题的转化，dp的方法都很巧妙。