题目传送门

之前一直没弄明白如何利用轻重链来维护答案，重新思考了一下以后明白了

题目大意

给出一棵树，树上每个点有点权，每个边有边权
2种操作
1.增加点权
2.改变根
Q次询问，每次询问完成当前操作后当前从当前根节点出发摘掉所有蘑菇的花费，每个蘑菇的花费为从根节点出发到蘑菇所在位置路径上距离根节点最近的边的边权，初始根节点为1

思路

赛场上想的是用线段树维护子树内蘑菇个数，对每个询问暴力枚举子树，后来想想如果给个菊花图，当场去世
正确的做法是用树链剖分维护
1.对于每一个点来说，与他相连的点有三种，重儿子，轻儿子，父亲
2.对于每个点所在的重链的头节点，又会是另一个点的轻儿子
3.对于某个节点的修改，显然只会影响到他祖先的答案
4.用线段树维护每个子树的大小，对于重儿子，线段树查询，对于轻儿子，在维护重链的同时直接统计，对于父亲的答案，用总蘑菇数减去根节点所在子树蘑菇数即可

如图，对于橙色节点的修改，会影响到的节点分别是绿色点和黑色点，其中绿色点是黑色点的轻儿子，橙色点是绿色点的重儿子
当我们从橙色点所在重链跳到黑色点所在重链的同时，将因为修改橙色点产生的贡献直接记录到黑色点，相当于黑色点的绿色轻儿子的答案被修改，显然隔壁空白轻儿子的答案不受橙色点的影响
这样我们就维护好了黑色点轻儿子的答案
对于绿色点，橙色点是它的重儿子，通过线段树上查询即可
在线段树上维护子树的大小，对于每个点的修改，会对他的所有祖先产生影响，所以对某个点相当于在线段树上对根节点到它的路径上所有点，区间修改单点查询
因为在轻重链剖分中，从一个节点到根节点最多经过次轻重链交替，用线段树维护的时间复杂度是，总复杂度为
这题就这样解决了

代码

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
// const int mod = 998244353;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 1e6 + 10;
struct EDGE
{
    int next, to, w;
} edge[maxn << 1];
int head[maxn], tot;
inline void addedge(int u, int v, int w)
{
    edge[tot] = {head[u], v, w};
    head[u] = tot++;
}
int fa[maxn], fv[maxn], top[maxn], sz[maxn], son[maxn], deep[maxn], dfn[maxn];
void dfs1(int u, int pre, int dep)
{
    sz[u] = 1;
    fa[u] = pre;
    deep[u] = dep;
    for (int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if(v==pre)
            continue;
        fv[v] = edge[i].w;
        dfs1(v, u, dep + 1);
        sz[u] += sz[v];
        if(sz[v]>sz[son[u]])
            son[u] = v;
    }
}
int idx;
void dfs2(int u,int tp)
{
    dfn[u] = ++idx;
    top[u] = tp;
    if(son[u])
        dfs2(son[u], tp);
    for (int i = head[u]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}

int n;

struct SEG
{
    ll val[maxn << 2];
    ll lazy[maxn << 2];
    void pushup(int root)
    {
        val[root] = val[root << 1] + val[root << 1 | 1];
    }
    void pushdown(int root, int l, int r)
    {
        if(lazy[root])
        {
            int mid = (l + r) >> 1;
            val[root << 1] += 1ll * lazy[root] * (mid - l + 1);
            val[root << 1 | 1] += 1ll * lazy[root] * (r - mid);
            lazy[root << 1] += lazy[root];
            lazy[root << 1 | 1] += lazy[root];
            lazy[root] = 0;
        }
    }
    void update(int root, int l, int r, int lt, int rt, int v)
    {
        if (l == lt && r == rt)
        {
            val[root] += 1ll * v * (r - l + 1);
            lazy[root] += v;
            return;
        }
        pushdown(root, l, r);
        int mid = (l + r) >> 1;
        if(rt<=mid)
            update(lson, lt, rt, v);
        else if (lt > mid)
            update(rson, lt, rt, v);
        else
        {
            update(lson, lt, mid, v);
            update(rson, mid + 1, rt, v);
        }
        pushup(root);
    }
    ll query(int root, int l, int r, int k)
    {
        if (l == r)
            return val[root];
        pushdown(root, l, r);
        int mid = (l + r) >> 1;
        if(k<=mid)
            return query(lson, k);
        else
            return query(rson, k);
    }
} seg;
ll ans[maxn];
ll sum = 0;
void update(int u, int v, int x)
{
    while (top[u] != top[v])
    {
        if (deep[top[u]] < deep[top[v]])
            swap(u, v);
        seg.update(1, 1, n, dfn[top[u]], dfn[u], x);
        ans[fa[top[u]]] += 1ll * fv[top[u]] * x;
        u = fa[top[u]];
    }
    if(deep[u]<deep[v])
        swap(u, v);
    seg.update(1, 1, n, dfn[v], dfn[u], x);
    sum += x;
}
ll ask(int u)
{
    ll res = 0;
    if(son[u])
        res += seg.query(1, 1, n, dfn[son[u]]) * fv[son[u]];
    res += ans[u];
    res += 1ll * fv[u] * (sum - seg.query(1, 1, n, dfn[u]));
    return res;
}

int main()
{
    read(n);
    memset(head, -1, sizeof head);
    int opt, u, v, w;
    for (int i = 1; i < n; ++i)
    {
        read(u), read(v), read(w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    int Q;
    read(Q);
    int rt = 1;
    for (int i = 0; i < Q; ++i)
    {
        read(opt);
        if (opt == 1)
        {
            read(u), read(w);
            update(1, u, w);
            // cnt[u] += w;
        }else
        {
            read(u);
            rt = u;
        }
        printf("%lld\n", ask(rt));
    }
}