传送门：【HDU】5029 Relief grain 题目分析：这题的方法太美妙了！ 首先看到这是一颗树，那么很容易想到树链剖分。然后想到可以将查询排个序，然后每一种查询执行完以后更新每个点的最优值。但是这样进行的复杂度太高！尤其是当z给的没有一样的时候尤其如此。 那么我们是否可以找到更加高效的算法？ 答案是肯定的！ 先简化一下问题，如果这些操作是在线段上进行的，我们怎么求解？

HDU - 5029 其实这道题最大的难点不是树链剖分，而是怎么维护某个点被那些颜色染过，染过多少次 如果在线段树维护的话，很难做到，估计得树套树，而且空间会炸 好在这题是离线的，可以使用差分的思想来维护 对一段区间[l,r]染色 c，相当于在这段区间左端点 l打上 c标志，右端点 r+1打上 -c标志 然后扫一遍整个区间 （依照 dfs序扫一遍整棵树），期间不断维护一颗线段树 线段树

题目链接：hdu 5029 Relief grain 题目大意：给定一棵树，然后每次操作在uv路径上为每个节点添加一个数w，最后输出每个节点个数最多的那个数。 解题思路：因为是在树的路径上做操作，所以基本就是树链剖分了。只不过以前是用一个数组即可维护值，这题要用 一个vector数组记录。过程中用线段树维护最大值。 #pragma comment(linker, "/STA