洛谷P1505 [国家集训队]旅游题解

题意：

给定一棵 \(n\) 个节点的树，边带权，编号 \(0 \sim n-1\)，需要支持五种操作：

C i w 将输入的第 \(i\) 条边权值改为 \(w\)

N u v 将 \(u,v\) 节点之间的边权都变为相反数

SUM u v 询问 \(u,v\) 节点之间边权和

MAX u v 询问 \(u,v\) 节点之间边权最大值

MIN u v 询问 \(u,v\) 节点之间边权最小值

保证任意时刻所有边的权值都在 \([-1000,1000]\) 内。

输入格式：

第一行一个正整数 \(n\)，表示节点个数。

接下来 \(n-1\) 行，每行三个整数 \(u,v,w\)，表示 \(u,v\) 之间有一条权值为 \(w\) 的边，描述这棵树。

然后一行一个正整数 \(m\)，表示操作数。

接下来 \(m\) 行，每行表示一个操作。

输出格式：

对于每一个询问操作，输出一行一个整数表示答案。

数据范围：

对于 \(100\%\) 的数据，\(1\le n,m \le 2\times 10^5\)。

简单的树剖。这道题的细节很多，比如边权最大值最小值不能直接 a=-b,b=-a 比较容易忽略。

由于询问的本质相同，所以我们可以直接写成一个函数，可以节省不少代码量。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

char op[15]; struct node { int sum, mx, mn, tag; } tr[N * 4];
int n,Q,pos=1,head[N],fa[N],dep[N],sz[N],son[N],top[N],id[N],a[N],pre[N];
struct Edge { int u,v,w,next; } e[N * 2];
void addEdge(int u,int v,int w) { e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
void dfs(int u,int f,int d)
{
    fa[u] = f; dep[u] = d; sz[u] = 1; int mx = -1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == f) continue; pre[v] = i;
        dfs(v,u,d+1); sz[u] += sz[v]; if(sz[v] > mx) { mx = sz[v], son[u] = v; }
    }
}
void dfs(int u,int ftop)
{
    static int tot = 0; top[u] = ftop; id[u] = ++tot;
    a[tot] = e[pre[u]].w; if(son[u]) dfs(son[u], ftop);
    for(int i = head[u]; i; i = e[i].next)
    { int v = e[i].v; if(v != fa[u] && v != son[u]) dfs(v,v); }
}
void push_up(int at)
{
    tr[at].sum = tr[ls(at)].sum + tr[rs(at)].sum;
    up(tr[at].mx = tr[ls(at)].mx, tr[rs(at)].mx); 
    down(tr[at].mn = tr[ls(at)].mn, tr[rs(at)].mn);
}
void build(int l,int r,int at)
{
    if(l == r) { return tr[at] = {a[l], a[l], a[l], 0}, void(0); }
    int mid = (l + r) >> 1; build(l,mid,ls(at)); build(mid+1,r,rs(at)); push_up(at);
}
void push_down(int at)
{
    if(tr[at].tag == 1)
    {
        node l = tr[ls(at)], r = tr[rs(at)]; tr[at].tag = 0;
        tr[ls(at)] = {-l.sum, -l.mn, -l.mx, l.tag ^ 1};
        tr[rs(at)] = {-r.sum, -r.mn, -r.mx, r.tag ^ 1};
    }
}
node merge(node x, node y)
{
    node c; c.sum = x.sum + y.sum; c.tag = 0;
    up(c.mx = x.mx, y.mx); down(c.mn = x.mn, y.mn);
    return c;
}
void Modify(int x,int v,int l = 1, int r = n, int at = 1)
{
    if(l == r) return tr[at] = {v,v,v}, void(0);
    push_down(at); int mid = (l + r) >> 1;
    (x <= mid) ? Modify(x,v,l,mid,ls(at)) : Modify(x,v,mid+1,r,rs(at)); push_up(at);
}
void update(int nl,int nr,int l = 1,int r = n, int at = 1)
{
    if(nl <= l && r <= nr)
    {
        tr[at] = {-tr[at].sum, -tr[at].mn, -tr[at].mx, tr[at].tag ^ 1};
        return;
    }
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, l, mid, ls(at));
    if(nr > mid) update(nl, nr, mid + 1, r, rs(at));
    push_up(at);
}
node query(int nl, int nr, int l = 1, int r = n,int at = 1)
{
    if(nl <= l && r <= nr) return tr[at];
    push_down(at); int mid = (l + r) >> 1;
    if(nl > mid) return query(nl, nr, mid + 1, r, rs(at));
    if(nr <= mid) return query(nl, nr, l, mid, ls(at));
    return merge(query(nl,nr,l,mid,ls(at)), query(nl,nr,mid+1,r,rs(at)));
}
void upRange(int x,int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        update(id[top[x]], id[x]); x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    if(id[x] < id[y]) update(id[x] + 1, id[y]);
}
node qRange(int x,int y)
{
    node res = {0, -INF, INF, 0};
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        res = merge(res, query(id[top[x]], id[x])); x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    if(id[x] < id[y]) res = merge(res, query(id[x] + 1, id[y]));
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1, u,v,w; i < n; i++)
    {
        cin >> u >> v >> w; ++u, ++v;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    dfs(1,0,1); dfs(1,1); build(1,n,1); cin >> Q; 
    for(int u,v,t; Q; Q--)
    {
        cin >> op >> u >> v; ++u; ++v;
        if(op[0] == 'C')
        {
            --u, --v, t = v, v = e[u * 2].v, u = e[u * 2].u;
            Modify(id[dep[u] > dep[v] ? u : v], t);
        }
        else if(op[0] == 'N') { upRange(u,v); }
        else if(op[0] == 'S') { cout << qRange(u,v).sum << '\n'; }
        else if(op[1] == 'A') { cout << qRange(u,v).mx << '\n'; }
        else { cout << qRange(u,v).mn << '\n'; }
    }
    return 0;
}