Problem

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

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

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

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

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

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

Solution

本题要求求带权重心。
求到带权重心之后，我们就可以通过带修动态点分治得到我们想要的答案。现在问题就在于怎么求带权重心。

由贪心的思想，求带权重心有个神奇的性质：
假设现在带权重心为 $u$，则该树强制以 $u$ 为根，$f_i$ 为以 $i$ 为根的子树的大小。
当 $2f_s>f_u$（s 为 u 的儿子）的时候，带权重心的范围肯定在以 s 为根的子树的范围内。

利用点分治的性质，在点分树上查询，可以保证每次范围缩小一半，即可以在 $\log n$ 的时间内查询。
现在问题在于，如果在点分树上查询，那么当往子树重点方向行进的话，可能子树的重点的子树并不是完整的。
解决办法是记录每个重点的子树的直接儿子。然后从直接儿子开始在点分树上往上每个点加 $f_u-f_s$ 直到该子树重点。

为什么这样是可行的？
首先我们保证查到的子树是按照深度递增的。也就是说直到直接儿子为止，这里面所有的点都保证了其子树是完整的。
其次保证与不完整的子树相邻。其它的子树都不与不完整的子树相邻，因此是可以不予理会的。直到它与不完整的子树相邻。

比较难解释其实。你甚至可能不懂这上面在说什么，但你可以自己先试着不管这些问题打打。

Code

// Code by ajcxsu
// Problem: battle

#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef vector<ll> vll;

template <typename T> void gn(T &x) {
    x=0;
    T pl=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') pl=(ch=='-'?-1:1), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl;
}

const int N=2e5+10, M=4e5+10;
int h[N], to[M], nexp[M], W[M], p=1;
inline void ins(int a,int b,int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++;}
int n,Q;
ll d[N], tot;

namespace Dis {
    int dep[N], son[N], fa[N], siz[N];
    int dfn[N], top[N], idx;
    ll wdep[N]; // 带权深度
    bool vis[N];
    void dfs1(int x, int k) {
        dep[x]=k, siz[x]=1;
        for(int u=h[x];u;u=nexp[u])
            if(!dep[to[u]]) {
                fa[to[u]]=x;
                dfs1(to[u], k+1);
                siz[x]+=siz[to[u]];
                if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
            }
    }
    void dfs2(int x,int t) {
        dfn[x]=++idx, top[x]=t;
        if(son[x]) dfs2(son[x], t);
        for(int u=h[x];u;u=nexp[u])
            if(!dfn[to[u]]) dfs2(to[u], to[u]);
    }
    int lca(int s,int t) {
        while(top[s]!=top[t]) {
            if(dep[top[s]]<dep[top[t]]) swap(s,t);
            s=fa[top[s]];
        }
        if(dep[s]>dep[t]) return t;
        return s;
    }
    void dfs3(int x,ll k) {
        wdep[x]=k, vis[x]=1;
        for(int u=h[x];u;u=nexp[u])
            if(!vis[to[u]]) dfs3(to[u], k+W[u]);
    }
    void init() { dfs1(1,1), dfs2(1,1), dfs3(1,0); }
    ll dis(int s, int t) {
        int l=lca(s,t);
        return wdep[s]+wdep[t]-wdep[l]*2;
    }
}

int siz[N], hvy, minn, S;
vector<ll> dt[N], wdt[N], son[N], bson[N]; // 子树点权和， 带权子树点权和， 子树的重点， 子树第一个节点
ll f[N]; // 子树点权总和
bool vis[N];
int fa[N];

void ghvy(int x,int fa) {
    siz[x]=1;
    int ma=0;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fa && !vis[to[u]]) {
            ghvy(to[u], x);
            siz[x]+=siz[to[u]];
            ma=max(ma, siz[to[u]]);
        }
    ma=max(ma, S-siz[x]);
    if(ma<minn) minn=ma, hvy=x;
}

void gans(int x) {
    vis[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!vis[to[u]]) {
            dt[x].push_back(0), wdt[x].push_back(0);
            ghvy(to[u],0), S=siz[to[u]], minn=INF, ghvy(to[u],0);
            son[x].push_back(hvy), bson[x].push_back(to[u]);
            fa[hvy]=x;
            gans(hvy);
        }
}

void changed(int x,ll add) {
    d[x]+=add; f[x]+=add;
    int from=x, u=x;
    x=fa[x];
    while(x) {
        for(int i=0;i<dt[x].size();i++)
            if(son[x][i]==from) dt[x][i]+=add, wdt[x][i]+=add*Dis::dis(u, x);
        f[x]+=add;
        from=x, x=fa[x];
    }
}

void pushup(int x,ll d,int aim) {
    while(x!=aim) {
        f[x]+=d;
        x=fa[x];
    }
    f[x]+=d;
}

int Find(int x) {
    for(int i=0;i<dt[x].size();i++)
        if(f[son[x][i]]*2>f[x]) {
            int res;
            ll p=f[x]-f[son[x][i]];
            pushup(bson[x][i], p, son[x][i]);
            res=Find(son[x][i]);
            pushup(bson[x][i], -p, son[x][i]);
            return res;
        }
    return x;
}

ll query(int x) {
    int from=-1, u=x;
    ll dis;
    ll ret=0;
    while(x) {
        dis=Dis::dis(x,u);
        for(int i=0;i<dt[x].size();i++)
            if(son[x][i]!=from) ret+=wdt[x][i]+dt[x][i]*dis;
        ret+=d[x]*dis;
        from=x, x=fa[x];
    }
    return ret;
}

int main() {
    gn(n), gn(Q);
    for(int i=0,u,v,w;i<n-1;i++) gn(u), gn(v), gn(w), ins(u,v,w), ins(v,u,w);
    Dis::init();
    int u,e;
    gans(1);
    while(Q--) {
        gn(u), gn(e);
        tot+=e;
        changed(u, e);
        printf("%lld\n", query(Find(1)));
    }
    return 0;
}