2020 CCPC-Wannafly Winter Camp Day2 (Div.1&2) F. 采蘑菇的克拉莉丝

树链剖分
考虑只枚举和父亲、重儿子的边，还差所有轻儿子的贡献。于是修改的时候，往根跳，在轻重链交替的时候往轻边父亲打标记即可根。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
#define fi first
#define se second
#define pb push_back
int n;
int siz[N],fa[N],son[N],a[N],cnt,to[N],de[N];
vector<pair<int,int>>v[N];
int L[N],R[N],cost[N];
void dfs1(int now,int pre,int d){
  siz[now]=1;
  fa[now]=pre;
  de[now]=d;
  int cn=-1;
  L[now]=++cnt;
  for(auto k:v[now]){
    if(k.fi==pre)continue;
    dfs1(k.fi,now,d+1);
    siz[now]+=siz[k.fi];
    cost[k.fi]=k.se;
    if(siz[k.fi]>cn){
      cn=siz[k.fi];
      son[now]=k.fi;
    }
  }
  R[now]=++cnt;
}
void dfs2(int now,int pre){
  to[now]=pre;
  if(!son[now])return ;
  dfs2(son[now],pre);
  for(auto k:v[now]){
    if(k.fi==fa[now]||k.fi==son[now])continue;
    dfs2(k.fi,k.fi);
  }
}

LL sum[N],laz[N];
void up(int l,int d){
  if(l==1)return;
  while(l>1){
    int ne=to[l];
    if(ne==1)return ;
    if(son[fa[ne]]!=ne){
      laz[fa[ne]]+=1ll*d*cost[to[l]];
    }
    l=fa[ne];
  }
}
LL t[N<<1];
void add(int x,int y){
  for(;x<=(n<<1);x+=x&-x){
    t[x]+=y;
  }
}
LL get(int x){
  LL res=0;
  for(;x;x-=x&-x){
    res+=t[x];
  }
  return res;
}
int main() {
  scanf("%d",&n);
  for(int i=1;i<n;i++){
    int s,t,w;
    scanf("%d%d%d",&s,&t,&w);
    v[s].pb(make_pair(t,w));
    v[t].pb(make_pair(s,w));
  }
  dfs1(1,0,0);
  dfs2(1,1);
  int q;
  scanf("%d",&q);
  int now=1;
  LL ev=0;
  for(int i=1;i<=q;i++){
    int o,l,r;
    scanf("%d%d",&o,&l);
    if(o==1){
      scanf("%d",&r);
      up(l,r);
      sum[l]+=r;
      add(L[l],r);
      ev+=r;
    }else{
      now=l;
    }
    LL ans=0;
    if(son[now])ans+=1ll*(get(R[son[now]])-get(L[son[now]]-1))*cost[son[now]];
    ans+=1ll*(ev-(get(R[now])-get(L[now]-1)))*cost[now];
    ans+=laz[now];
    printf("%lld\n",ans);
  }
  return 0;
}