F--采蘑菇的克拉莉丝（重轻链的应用）

题：https://ac.nowcoder.com/acm/contest/4010/F

题意：给定一个树，有俩种操作，第一种节点v增加x个蘑菇；第二种根节点变为v。问每次操作完后，树上所有蘑菇走到根节点的代价。（每个蘑菇的代价为蘑菇与根节点连边最近的一条）。

分析：对于每个操作后的根节点，我们可以把答案分为3部分，第一部分为重链的贡献，第二部分为轻链的贡献，第三部分为根节点父亲以上蘑菇的贡献。

　　　对于第一部分，我们需要将重链上的蘑菇数加到线段树上，方便单点查询，具体的，节点v增加x，就要节点v依据重链跳，然后将重链上的节点加上x；

　　　对于第二部分，在第一部分重链跳的过程中，会有轻链的转换，我们就在这时把轻链的部分加到父亲去。

　　　对于第三部分，只要所有蘑菇减去根节点的重轻链孩子的数目  乘上  根节点到父亲的边权即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int M=1e6+5;
const int mod=998244353;
struct node{
    int v,w;
};
vector<node>g[M];
int n,tot,sz[M],fa[M],id[M],son[M],top[M];
ll sum,edgew[M],tr[M<<2],lz[M<<2],lightnum[M],ans1[M],cnt[M];
void dfs1(int u,int f){
    sz[u]=1,fa[u]=f;
    for(auto now:g[u]){
        if(now.v!=f){
            dfs1(now.v,u);
            edgew[now.v]=now.w;
            sz[u]+=sz[now.v];
            if(sz[now.v]>sz[son[u]])
                son[u]=now.v;
        }
    }
}
void dfs2(int u,int tp){
    id[u]=++tot,top[u]=tp;
    if(son[u])
        dfs2(son[u],tp);
    for(auto now:g[u]){
        if(now.v!=fa[u]&&now.v!=son[u])
            dfs2(now.v,now.v);
    }
}
void up(int root){
    tr[root]=tr[root<<1]+tr[root<<1|1];
}
void pushdown(int root){
    if(lz[root]){
        tr[root<<1]+=lz[root];
        tr[root<<1|1]+=lz[root];
        lz[root<<1]+=lz[root];
        lz[root<<1|1]+=lz[root];
        lz[root]=0;
    }
}
void update(int L,int R,ll x,int root,int l,int r){
    if(L<=l&&r<=R){
        tr[root]+=x;
        lz[root]+=x;
        return ;
    }
    pushdown(root);
    int midd=(l+r)>>1;
    if(L<=midd)
        update(L,R,x,lson);
    if(R>midd)
        update(L,R,x,rson);
    up(root);
}
ll query(int pos,int root,int l,int r){
    if(l==r){
        return tr[root];
    }
    int midd=(l+r)>>1;
    pushdown(root);
    if(pos<=midd)
        return query(pos,lson);
    else
        return query(pos,rson);
}
void solve(int u,ll x){
    while(u){
        update(id[top[u]],id[u],x,1,1,n);
        u=top[u];
        ans1[fa[u]]+=1ll*edgew[u]*x;
        lightnum[fa[u]]+=x;
        u=fa[u];
    }
}
int main(){
    scanf("%d",&n);
    for(int u,v,w,i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        g[u].pb(node{v,w});
        g[v].pb(node{u,w});
    }
    dfs1(1,0);
    dfs2(1,1);
    int m,rt=1;
    scanf("%d",&m);
    while(m--){
        int op;
        scanf("%d",&op);
        if(op==1){
            int v;
            ll x;
            scanf("%d%lld",&v,&x);
            cnt[v]+=x;
            sum+=x;
            solve(v,x);
        }
        else
            scanf("%d",&rt);
        ll ans=0;
        ll heavynum=0;
        if(id[son[rt]])
            heavynum=query(id[son[rt]],1,1,n);
        ///加上重孩子部分
        ans+=heavynum*edgew[son[rt]];
        ///加上其他孩子部分
        ans+=ans1[rt];
        ///加上父亲以上的部分
        ll othernum=sum-heavynum-lightnum[rt]-cnt[rt];
        ans+=othernum*edgew[rt];
        printf("%lld
",ans);
    }
    return 0;
}