先在线段树上二分得到 满足子树点权和>=总点权/2的 dfs序最大的点x

之后再考虑计算带权距离和，即 $ans(x)= \sum_{i} dis(i,x) * v[i]$

因为$dis(i,x)=deep[i]+deep[x]-2*deep[lca]$

所以$ans(x)=(\sum_{i} deep[i] * v[i]) + (deep[x]*\sum_{i} v[i]) -2*(\sum_{i} v[i]*deep[lca]) $

前两项直接维护

最后一个式子怎么算呢

就是每次 $v[i]$+=$x$ 就把$i$到根的路径上的点的$add$全部+=$x$

查询$ans(x)$时 就查询x到根的$\sum_{i} add[i]*(deep[i]-deep[fa[i]])$

线段树预处理区间$\sum_{i}(deep[i]-deep[fa[i]])$后可以维护

时间$O(nlog^2)$ 跑的还是挺快的

# pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define pb push_back
const int ch_top=1e7;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
int read()
{
    while(*++now_r<'-');
    if(*now_r=='-')
    {
        int x=*++now_r-'0';
        while(*++now_r>='0')x=x*10+*now_r-'0';
        return -x;
    }
    int x=*now_r-'0';
    while(*++now_r>='0')x=x*10+*now_r-'0';
    return x;
}
void write(ll x)
{
    static char st[20];static int top;
    if(!x)*++now_w='0';
    else
    {
        do{st[++top]='0'+x%10;}while(x/=10);
        do{*++now_w=st[top];}while(--top);
    }
    *++now_w='\n';
}

const int N=1e5+5,T=N*4;
struct edge
{
    int to,w;
};
int n,m;
vector<edge>lk[N];
int fa[N],deep[N],sz[N],son[N],top[N],dfn[N],tot;
int q[N];
void dfs(int x,int fr,int dep)
{
    fa[x]=fr;deep[x]=dep;sz[x]=1;
    vector<edge>::iterator i=lk[x].begin();
    while(i!=lk[x].end())
    {
        int y=i->to;
        if(y==fr){++i;continue;}
        dfs(y,x,dep+i->w);
        sz[x]+=sz[y];
        if(sz[y]>sz[son[x]])son[x]=y;
        ++i;
    }
}
void dfs2(int x,int ntop)
{
    q[dfn[x]=++tot]=x;top[x]=ntop;
    if(!son[x])return ;
    dfs2(son[x],ntop);
    for(vector<edge>::iterator i=lk[x].begin();i!=lk[x].end();++i)
    {
        int y=i->to;
        if(y==son[x]||y==fa[x])continue;
        dfs2(y,y);
    }
}

int x,w;
ll xs,s;
#define mid (l+r>>1)
#define cl (k*2)
#define cr (cl+1)
namespace seg
{
int ad[T],mx[T];ll s[T],xs[T];
int ql,qr;
inline void _add(int k,int x)
{
    ad[k]+=x;mx[k]+=x;
    xs[k]+=s[k]*x;
}
inline void down(int k)
{
    if(ad[k]){_add(cl,ad[k]);_add(cr,ad[k]);ad[k]=0;}
}
inline void up(int k)
{
    mx[k]=max(mx[cl],mx[cr]);
    xs[k]=xs[cl]+xs[cr];
}
void add(int k,int l,int r)
{
    if(ql<=l&&qr>=r){_add(k,w);return ;}
    down(k);
    if(ql<=mid)add(cl,l,mid);
    if(qr>mid)add(cr,mid+1,r);
    up(k);
}
void add(int l,int r)
{
    ql=l;qr=r;
    add(1,1,n);
}
void init(int k,int l,int r)
{
    if(l==r)
    {
        s[k]=deep[q[l]]-deep[fa[q[l]]];
        return ;
    }
    init(cl,l,mid);init(cr,mid+1,r);
    s[k]=s[cl]+s[cr];
}
int qiu(const ll &x)
{
    int k=1,l=1,r=n;
    while(l!=r)
    {
        down(k);
        if(mx[cr]>=x) {k=cr;l=mid+1;}
        else {k=cl;r=mid;}
    }
    return l;
}

ll ans;
void qiu(int k,int l,int r)
{
    if(ql<=l&&qr>=r){ans+=xs[k];return ;}
    down(k);
    if(ql<=mid)qiu(cl,l,mid);
    if(qr>mid)qiu(cr,mid+1,r);
}
ll qiu(int l,int r)
{
    ql=l;qr=r;ans=0;
    qiu(1,1,n);
    return ans;
}
};
void add_to_rt(int x)
{
    while(x)
    {
        int f=top[x];
        seg::add(dfn[f],dfn[x]);
        x=fa[f];
    }
}
ll qiu_s(int x)
{
    ll ans=0;
    while(x)
    {
        int f=top[x];
        ans+=seg::qiu(dfn[f],dfn[x]);
        x=fa[f];
    }
    return ans;
}

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    fread(ch,1,ch_top,stdin);
    n=read();m=read();
    rep(i,1,n-1)
    {
        int a=read(),b=read(),c=read();
        lk[a].pb((edge){b,c});lk[b].pb((edge){a,c});
    }
    dfs(1,0,0);
    dfs2(1,1);
    seg::init(1,1,n);
    while(m--)
    {
        x=read();w=read();
        add_to_rt(x);
        xs+=(ll)deep[x]*w;
        s+=w;
        x=q[seg::qiu(s+1>>1)];
        write(xs+s*deep[x]-2*qiu_s(x));
    }
    fwrite(ch,1,now_w-ch+1,stdout);
}