题目描述

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

在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。 整个地图是一个树结构，一共有n块空地，这些空地被n-1条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。

在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。 如果补给站在点u上，并且空地v上有dv个单位的军队，那么幽香每天就要花费dv*dist(u,v)的金钱来补给这些军队。

由于幽香需要补给所有的军队，因此幽香总共就要花费为Sigma(Dv*dist(u，v),其中1<=V<=N)的代价。其中dist(u,v)表示u个v在树上的距离（唯一路径的权和）。

因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动他的补给站从而省一些钱。

但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？ 你可以假定一开始所有空地上都没有军队。

输入输出格式

输入格式：

第一行两个数n和Q分别表示树的点数和幽香操作的个数，其中点从1到n标号。 接下来n-1行，每行三个正整数a,b,c，表示a和b之间有一条边权为c的边。 接下来Q行，每行两个数u,e，表示幽香在点u上放了e单位个军队（如果e<0，就相当于是幽香在u上减少了|e|单位个军队，说白了就是du←du+e）。数据保证任何时刻每个点上的军队数量都是非负的。

输出格式：

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

输入输出样例

输入样例#1： 

10 51 2 12 3 12 4 11 5 12 6 12 7 15 8 17 9 11 10 13 12 18 13 14 1

输出样例#1： 

01456

说明

对于所有数据，1<=c<=1000, 0<=|e|<=1000, n<=10^5, Q<=10^5 非常神奇的是，对于所有数据，这棵树上的点的度数都不超过20，且N，Q>=1

题解

　　噩梦……真的噩梦……我快被幽香给玩死了……

　　用这道题来理解动态淀粉质点分治的（因为当初捉迷藏那题直接学岛娘的括号序列……就没去再打一遍……），然而题解大佬们都直接默认我们已经会动态点分然后直接上……结果我昨天看了一个晚上才弄懂……然后今天又花了一个早上码完，交上去竟然1A了不可思议

　　先说一下什么是动态点分治吧。对于一般的点分治，因为我们每一次都找出重心，所以每一次递归往左右子树找的时候深度不会超过$O(log n)$层。但是如果有了修改操作怎么办呢？每修改一次点分一次么？那怕是得T飞

　　我们来看一下这道题目，它的每一次修改，更改的只有点权，树的结构是没有变化的（如果有的话怕是只能上LCT了……），也就是说，每一次点分的时候找到的重心是不会改变的。那么，我们可不可以把点分治每一层的重心给连成一棵树呢？因为点分的递归层数只有$O(log n)$层，所以这棵点分树的深度也是$O(log n)$的

　　那么考虑一下在每一个点分树的节点维护什么东西，对于每一个节点，我们维护他的子树中的所有信息，也就是在原树中它被选为重心时的那个子树的所有信息。修改的时候，只要从一个点开始在点分树里往上跳，并不断更新信息即可。查询一个点的时候，点分树里跳，不断考虑与父亲之间的贡献就好了。

　　上面那一段看不懂也没关系，因为我只是在口胡，假装自己已经很懂动态点分的样子

　　那么我们具体来分析一下这道题目我们要维护什么

　　题目要求使$\sum d_v*dis(u,v)$最小，其中$d_v$为$v$点的点权，$dis(u,v)$为原树中$u,v$两点的距离。题目要求就是求带权重心。假设我们当前已经选定了点$v$为答案，那么考虑它的一个子节点$w$，如果把补给站从点$v$转移到$w$，那么$w$的所有子树内的点到补给站的距离少了$dis(v,w)$，而其他所有点到补给站的距离多了$dis(v,w)$。我们假设$sum_v[v]$为$v$的子树内的点权和，那么答案总共的变化量是$$dis(u,v)*(sum_v[v]-sum_v[w]-sum_v[w])$$

　　不难发现，当$sum_v[w]*2>sum_v[v]$的时候，答案的变化量是小于零的，也就是说代价减小，可以变得更优。而且，满足这样条件的点$w$最多只有一个

　　那么我们可以每一次选定一个点，然后看看往他的哪个子树走更优，如果没有说明他自己就已经是最优的了。这样不断下去肯定能找到答案。

　　但是由于原图可能是一条链，要怎么做才能保证复杂度呢？我们选择在点分树上走，每一次都跳到它下一层的重心，这样可以保证层数最多只有$O(log n)$

　　然后考虑如何维护答案。不难发现，对于点分树上一个点$v$，它的子树中的点就是在点分治时它被选为重心时的那棵树上的点。考虑点分树上的一对父子$u,v$，我们设$sum_a[v]$表示$v$的子树内的所有点到他的代价之和，$sum_b[v]$为$v$的子树内的所有点到$v$点父亲（也就是点$u$）的距离之和，$sum_v[v]$还是表示子树的点权之和。那么我们设答案已经选定为点$v$，加上$u$的不包括$v$的子树后答案就是$sum_a[v]-sum_b[v]+sum_a[u]+sum_v[u]*dis(u,v)$。于是只要在点分树上不断找父亲并合并，就可以知道答案了

　　然后我们只要能在修改时维护好这三个数组就可以了！！！

　　至于修改时如何维护呢？我们修改一个点之后，然后不断在点分树上往父节点跳，并不断更新即可。查询的时候也是，不断跳并合并答案

　　然后又新学会了一招，用$RMQ O(1)$查询$LCA$（只会倍增和树剖的我瑟瑟发抖），总时间复杂度$O(nlog^2n)$

1 //minamoto  2 #include
     
        3 #include
      
         4 #include
       
          5 #define ll long long  6 #define N 100005  7 #define inf 0x3f3f3f3f  8 #define rint register int  9 using namespace std; 10 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 11 char buf[1<<21],*p1=buf,*p2=buf; 12 template
        
         inline bool cmax(T&a,const T&b){
   return a
         
          1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 27     while(z[++Z]=x%10+48,x/=10); 28     while(sr[++C]=z[Z],--Z);sr[++C]='\n'; 29 } 30 struct G{ 31     int head[N],Next[N<<1],edge[N<<1],ver[N<<1],tot; 32     G(){tot=0;memset(head,0,sizeof(head));} 33     inline void add(int u,int v,int e){ 34         ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e; 35     } 36 }T1,T2; 37 int n,q,st[N<<1][18],logn[N<<1],bin[25],tp; 38 ll sum,ans,d[N],dis1[N],dis2[N],sumv[N]; 39 int dfn[N],num; 40 void dfs1(int u,int fa){ 41     st[dfn[u]=++num][0]=d[u]; 42     for(int i=T1.head[u];i;i=T1.Next[i]){ 43         int v=T1.ver[i]; 44         if(v==fa) continue; 45         d[v]=d[u]+T1.edge[i],dfs1(v,u),st[++num][0]=d[u]; 46     } 47 } 48 inline ll LCA(int a,int b){ 49     if(dfn[a]>dfn[b]) a^=b^=a^=b; 50     int k=logn[dfn[b]-dfn[a]+1]; 51     return min(st[dfn[a]][k],st[dfn[b]-bin[k]+1][k])<<1; 52 } 53 inline ll dis(int a,int b){
   return d[a]+d[b]-LCA(a,b);} 54 int sz[N],son[N],size,rt,fa[N];bool vis[N]; 55 void dfs2(int u,int fa){ 56     sz[u]=1,son[u]=0; 57     for(int i=T1.head[u];i;i=T1.Next[i]){ 58         int v=T1.ver[i]; 59         if(vis[v]||v==fa) continue; 60         dfs2(v,u),sz[u]+=sz[v],cmax(son[u],sz[v]); 61     } 62     cmax(son[u],size-sz[u]); 63     if(son[u]
          
           >1]+1;106 for(rint i=1;i