=== 简述题意 ===

m 个 tourist 想要在树上旅游，每个 tourist 有 3 个可选目的地，每个目的地有代价。现在要求，给出一种选择方案，使得没有旅游路线相交，并且最小化此时的代价。

=== 题解 ===

可以发现，对于一个 tourist ，他自己的三条路线也是互斥的。因此，问题转化为了现有 3m 条路径，取出不相交的若干条路径，使得代价最小。我们将路径的权值进行转化 $w' = (m+1)10^6 - w$ 此时变为需要 w' 最大。容易发现，最优解一定会尽可能的多选路径，同时，可以通过最终答案 $ans >= m*m10^6$ 来得到此时的最优解选择了 m 条路径，满足题意要求。

问题转化为了选择不相交的路径，使得路径权值和最大。奇妙的，这个答案与另一个问题相等：为尽可能少的点赋权，使得每条路径上的点权和至少为路径权值，此时赋值之和即为答案。很奇妙，感性理解后感觉很有道理。

现在我们需要得到一条路径上的点权和，并且需要支持修改操作。可以发现使用dfn搭配树状数组。f[u] 维护 u 到根的路径权值和即可，使用差分思想。