萌新求助树剖。 #11AC

#include <iostream>
#include <cstdio>
#define MAXN 200005
#define ll long long
#define cjb 1145141919810843
using namespace std;
int n, m;
ll w[MAXN];
int eu[MAXN]; // 边对应的点的编号

namespace F_star
{
    int cnte = 0, head[MAXN];
    struct edge
    {
        int to, nxt, dis;
    }e[MAXN << 1];
    void adde(int u, int v, int w)
    {
        e[++cnte].to = v;
        e[cnte].dis = w;
        e[cnte].nxt = head[u];
        head[u] = cnte;
    }
}using namespace F_star;

namespace shupou
{
    int T;
    int fa[MAXN], siz[MAXN], son[MAXN];
    int id[MAXN], top[MAXN], dep[MAXN];
    ll dis[MAXN];
    
    int LCA(int, int);
    void dfs1(int, int);
    void dfs2(int, int);
}using namespace shupou;

namespace Leitree
{   
    struct tree
    {
        int l, r, len;
        ll mi = 0, mx = 0;
        ll sum = 0;
        ll Lz = 1;
    }t[MAXN << 2];
    #define ls(i) (i << 1)
    #define rs(i) (i << 1 | 1)
    void push_up(int);
    void push_down(int);
    void build(int, int, int);
    void change(int, int, ll);
    void mul(int, int, int, ll);
    ll query_sum(int, int, int);
    ll query_max(int, int, int);
    ll query_min(int, int, int);
    
}using namespace Leitree;

void MMM(int u, int v)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        mul(1, id[top[u]], id[u], -1);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    mul(1, id[u]+1, id[v], -1);
}

ll QQQ_sum(int u, int v)
{
    ll ans = 0;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        ans += query_sum(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    ans += query_sum(1, id[u]+1, id[v]);
    return ans;
}

ll QQQ_max(int u, int v)
{
    ll ans = -cjb;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        ans = max(ans ,query_max(1, id[top[u]], id[u]));
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    ans = max(ans, query_max(1, id[u]+1, id[v]));
    return ans;
}

ll QQQ_min(int u, int v)
{
    ll ans = cjb;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        ans = min(ans ,query_min(1, id[top[u]], id[u]));
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    ans = min(ans, query_min(1, id[u]+1, id[v]));
    return ans;
}

int main()
{
    freopen("P1505.in", "r", stdin);
    freopen("P1515.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        int u, v; ll  w;
        scanf("%d%d%lld", &u, &v, &w);
        u++; v++;
        adde(u, v, w);
        adde(v, u, w);
    }    
    dfs1(1, 0); dfs2(1, 1); build(1, 1, T);
    
    scanf("%d", &m);
    for(int i = 1; i <= m; i++)
    {
        char op[5]; scanf("%s", op+1);
        if(op[1] == 'C')
        {
			int x; ll y; scanf("%d%lld", &x, &y);
            change(1, id[eu[x]], y);
        }
        else if(op[1] == 'N')
        {
			int x, y; scanf("%d%d", &x, &y);
            x++, y++;
            MMM(x, y);
        }
        else if(op[1] == 'S')
        {
			int x, y; scanf("%d%d", &x, &y);
            x++, y++;
            printf("%lld\n", QQQ_sum(x, y));
        }
        else if(op[2] == 'A')
        {
			int x, y; scanf("%d%d", &x, &y);
            x++, y++;
            printf("%lld\n", QQQ_max(x, y));
        }
        else
        {
			int x, y; scanf("%d%d", &x, &y);
            x++, y++;
            printf("%d\n", QQQ_min(x, y));
        }
    } 
    return 0;
}

namespace shupou
{
    void dfs1(int u, int dad)
    {
        siz[u] = 1; fa[u] = dad; dep[u] = dep[dad] + 1;
        for(int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].to; if(v == dad) continue;
            w[v] = e[i].dis; eu[(i+1)/2] = v;
            dfs1(v, u); siz[u] += siz[v];
            if(siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    
    void dfs2(int u, int tup)
    {
        id[u] = ++T; dis[T] = w[u]; top[u] = tup;
        if(son[u]) dfs2(son[u], tup);
        for(int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            if(v == fa[u] || v == son[u])
            continue;
            dfs2(v, v);
        }
    }
    
    int LCA(int u, int v)
    {
        while(top[u] != top[v])
        {
            if(dep[top[u]] > dep[top[v]])
            u = fa[top[u]];
            else
            v = fa[top[v]];
        }
        return dep[u] < dep[v] ? u : v;
    }
}

namespace Leitree
{
    void push_up(int i)
    {
        t[i].sum = t[ls(i)].sum + t[rs(i)].sum;
        t[i].mx = max(t[ls(i)].mx, t[rs(i)].mx);
        t[i].mi = min(t[ls(i)].mi, t[rs(i)].mi);
    }
    
    void push_down(int i)
    {
        if(t[i].Lz == 1) return;
        t[ls(i)].sum *= t[i].Lz; t[rs(i)].sum *= t[i].Lz;
        t[ls(i)].mx *= t[i].Lz; t[ls(i)].mi *= t[i].Lz;
        t[rs(i)].mx *= t[i].Lz; t[rs(i)].mi *= t[i].Lz;
        t[ls(i)].mx = max(t[ls(i)].mx, t[ls(i)].mi);
        t[rs(i)].mx = max(t[rs(i)].mx, t[rs(i)].mi);
        t[ls(i)].mi = min(t[ls(i)].mi, t[ls(i)].mx);
        t[rs(i)].mi = min(t[rs(i)].mi, t[rs(i)].mx);
        t[rs(i)].Lz *= t[i].Lz; t[ls(i)].Lz *= t[i].Lz;
        t[i].Lz = 1;
    }
    
    void build(int i, int l, int r)
    {
        t[i].l = l;  t[i].r = r;
        if(l == r)
        {
            t[i].sum = t[i].mx = t[i].mi = dis[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(i), l, mid);
        build(rs(i), mid+1, r);
        push_up(i);
    }

    void change(int i, int pos, ll val)
    {
        if(t[i].l == pos && t[i].r == pos)
        {
            t[i].sum = t[i].mx = t[i].mi = val;
            t[i].Lz = 1;
            return;
        }
        push_down(i);
        int mid = (t[i].l + t[i].r) >> 1;
        if(pos <= mid) change(ls(i), pos, val);
        else change(rs(i), pos, val);
        push_up(i);
    }

    void mul(int i, int l, int r, ll val)
    {
        if(t[i].l >= l && t[i].r <= r)
        {
            t[i].sum *= val;
            t[i].mx *= val;
            t[i].mi *= val;
            t[i].mx = max(t[i].mx, t[i].mi);
            t[i].mi = min(t[i].mi, t[i].mx);
            t[i].Lz *= val;
            return;
        } 
        push_down(i);
        if(t[ls(i)].r >= l) mul(ls(i), l, r, val);
        if(t[rs(i)].l <= r) mul(rs(i), l, r, val);
        push_up(i);
    }
    
    ll query_sum(int i, int l ,int r)
    {
        if(t[i].l >= l && t[i].r <= r) return t[i].sum;
        ll ans = 0;
        push_down(i);
        if(t[ls(i)].r >= l) ans += query_sum(ls(i), l, r);
        if(t[rs(i)].l <= r) ans += query_sum(rs(i), l, r);
        push_up(i);
        return ans;
    }
    ll query_max(int i, int l ,int r)
    {
        if(t[i].l >= l && t[i].r <= r) return t[i].mx;
        ll ans = -cjb;
        push_down(i);
        if(t[ls(i)].r >= l) ans = max(ans, query_max(ls(i), l, r));
        if(t[rs(i)].l <= r) ans = max(ans, query_max(rs(i), l, r));
        push_up(i);
        return ans;
    }

    ll query_min(int i, int l ,int r)
    {
        if(t[i].l >= l && t[i].r <= r) return t[i].mi;
        ll ans = cjb;
        push_down(i);
        if(t[ls(i)].r >= l) ans = min(ans, query_min(ls(i), l, r));
        if(t[rs(i)].l <= r) ans = min(ans, query_min(rs(i), l, r));
        push_up(i);
        return ans;
    }
}