题目描述

傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。

在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。

整个地图是一个树结构，一共有$n$块空地，这些空地被$n-1$条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。 如果补给站在点$u$上，并且空地$v$上有$d_v$个单位的军队，那么幽香每天就要花费$d_v \times dist(u,v)$的金钱来补给这些军队。由于幽香需要补给所有的军队，因此幽香总共就要花费为$\sum_{v} {d_v dist(u,v)}$的代价。其中$dist(u,v)$表示$u$个$v$在树上的距离（唯一路径的权和）。

因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动他的补给站从而省一些钱。但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？ 你可以假定一开始所有空地上都没有军队。

输入格式

第一行两个数$n$和$Q$分别表示树的点数和幽香操作的个数，其中点从1到$n$标号。 接下来$n-1$行，每行三个正整数$a,b,c$，表示$a$和$b$之间有一条边权为$c$的边。

接下来$Q$行，每行两个数$u,e$，表示幽香在点$u$上放了$e$单位个军队（如果$e \lt 0$，就相当于是幽香在$u$上减少了$|e|$单位个军队，说白了就是$du = du+e$）。数据保证任何时刻每个点上的军队数量都是非负的。

$1 \le c \le 1000, 0 \le |e| \le 1000, n \le 10 ^ 5, Q \le 10 ^ 5$

输出格式

对于幽香的每个操作，输出操作完成以后，每天的最小花费，也即如果幽香选择最优的补给点进行补给时的花费。

题目解析

据说数据比较弱，可以$n ^ 2$过十万，不明觉厉~

考虑点分治。我们将分治结构建成一棵分治树，在每个结点维护分治结构内的点权和，带权距离和。修改时只会影响到$O(\log n)$层结点，简单维护一下就好，复杂度$O(\log n)$。询问时我们从根出发，先看一下当前点是否是带权重心，如果不是，那么重心一定在带权距离和最大的分治子结构里。询问一次某点的带权距离和$O(\log n)$，经过的点有$O(\log n)$层，故复杂度为$O(\log ^ 2 n)$。总时间复杂度$O(n \log ^ 2 n)$。