【国家集训队】旅游-题解

题意描述

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

1. C i w 将输入的第 $i$ 条边权值改为 $w$
2. N u v 将 $u,v$ 节点之间的边权都变为相反数
3. SUM u v 询问 $u,v$ 节点之间边权和
4. MAX u v 询问 $u,v$ 节点之间边权最大值
5. MIN u v 询问 $u,v$ 节点之间边权最小值

保证任意时刻所有边的权值都在$[−10^3 , 10^3]$ 内。

---

输入格式

第一行一个正整数 $n$，表示节点个数。

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

然后一行一个正整数 $m$，表示操作数。

接下来 $m$ 行，每行表示一个操作。

---

输出格式

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

---

Input & Output ‘s examples

Input ‘s eg 1

3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2

Output ‘s eg 1

3
2
1
-1
5
3

---

数据范围和约定

对于$100\%$的数据：$1 ≤ n, m ≤ 2 \times 10^5$。

---

分析

养 生 题 目 警 告。

题目中要求我们维护一棵树上信息，且为区间操作，很容易想到树剖维护。

但问题在于树剖只能维护点权，但本题要求维护边权。

因此，我们考虑如何把边权转为点权。

容易发现，树上的一个点仅有一个父亲，且该点与其父亲之间仅有一条边相连。

因此我们可以将该点与其父亲相连边的边权转移至该点上。由于一个点只有一个父亲，因此这样的转移是唯一的。

但这样会出现一个问题：在查询时，我们会多算两节点的$\text{LCA}$到$\text{LCA}$父亲的一条边。

因此，当两节点在同一条重链上时，左端点需要右移一位以减去多算的边。

还有就是操作$2$的一点细节：取相反数后，原本的区间最大值会变成最小值，区间最小值会变成区间最大值。在做pushdown的时候需要特别注意。

然后是树剖版子题了……

至于代码的话，也就大约10kb，往死里写就完事了

---

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 200001;
const int HA = 998244353;
const int INF = 2147483647;
const long long INFL = 9223372036854775807;

struct Edge{
    int to , last , dis;
}edge[M << 1];

int edge_num;
int head[M << 1];

I void add_edge(int from , int to , int dis){
    edge[++ edge_num] = (Edge){to , head[from] , dis}; head[from] = edge_num;
    edge[++ edge_num] = (Edge){from , head[to] , dis}; head[to] = edge_num;
}

int dep[M] , fa[M] , son[M] , size[M] , val[M];

int dfs1(int x , int f , int deep){
    dep[x] = deep;
    fa[x] = f;
    int maxn = -1;
    PE(i , x){
        int to = edge[i].to , dis = edge[i].dis;
        if(to == f) continue;
        val[to] = dis;
        size[x] += dfs1(to , x , deep + 1);
        if(size[to] > maxn){
            maxn = size[to];
            son[x] = to;
        }
    }
    return size[x];
}

int tp[M] , dfn[M] , a[M] , cnt;

void dfs2(int x , int topf){
    dfn[x] = ++ cnt;
    a[cnt] = val[x];
    tp[x] = topf;
    if(!son[x]) return;
    dfs2(son[x] , topf);
    PE(i , x){
        int to = edge[i].to;
        if(!dfn[to]){
            dfs2(to , to);
        }
    }
}

namespace Segment_tree{
    #define lson(x) x << 1
    #define rson(x) x << 1 | 1

    struct Node{
        int l , r , len;
        int num , add , maxn , minn , opo;
    }node[M << 2];

    I void pushup(int x){
        node[x].num = (node[lson(x)].num + node[rson(x)].num);
        node[x].maxn = max(node[lson(x)].maxn , node[rson(x)].maxn);
        node[x].minn = min(node[lson(x)].minn , node[rson(x)].minn);
    }

    I void pushdown(int x){
        if(node[x].opo != 1){
            node[lson(x)].opo *= -1; node[lson(x)].num *= -1;
            node[rson(x)].opo *= -1; node[rson(x)].num *= -1;
            int lmax = node[lson(x)].maxn , lmin = node[lson(x)].minn;
            int rmax = node[rson(x)].maxn , rmin = node[rson(x)].minn;
            node[lson(x)].maxn = -lmin; node[lson(x)].minn = -lmax;
            node[rson(x)].maxn = -rmin; node[rson(x)].minn = -rmax;
            node[x].opo = 1;
        } 
        if(node[x].add != 0){
            node[lson(x)].add += node[x].add;
            node[lson(x)].num += node[x].add * node[lson(x)].len;
            node[rson(x)].add += node[x].add;
            node[rson(x)].num += node[x].add * node[rson(x)].len;
            node[x].add = 0;
        }
    }

    void build(int x , int l , int r){
        node[x].l = l; node[x].r = r;
        node[x].len = (r - l + 1);
        node[x].opo = 1;
        if(l == r){
            node[x].num = node[x].maxn = node[x].minn = a[l];
            return ;
        }
        int mid = (node[x].l + node[x].r) >> 1;
        build(lson(x) , l , mid);
        build(rson(x) , mid + 1 , r);
        pushup(x);
    }

    void point_change(int x , int q, int change){
        if(node[x].l == node[x].r){
            node[x].num = change;
            node[x].add = 0;
            node[x].maxn = node[x].minn = change;
            return;
        }
        pushdown(x);
        int mid = (node[x].l + node[x].r) >> 1;
        if(q <= mid){
            point_change(lson(x) , q , change);
        }
        else{
            point_change(rson(x) , q , change);
        }
        pushup(x);
    }

    void range_add(int x , int ql , int qr , int add){
        if(ql <= node[x].l && node[x].r <= qr){
            node[x].add += add;     
            node[x].num += node[x].len * add;
            return ;
        }
        pushdown(x);
        int mid = (node[x].l + node[x].r) >> 1;
        if(ql <= mid){
            range_add(lson(x) , ql , qr , add);
        }
        if(mid + 1 <= qr){
            range_add(rson(x) , ql , qr , add);
        }
        pushup(x);
    }

    void range_opposite(int x , int ql , int qr){
        if(ql <= node[x].l && node[x].r <= qr){
            node[x].opo *= -1;
            node[x].num *= -1;
            int maxn = node[x].maxn , minn = node[x].minn;
            node[x].maxn = -minn; node[x].minn = -maxn;
            return ;
        }
        pushdown(x);
        int mid = (node[x].l + node[x].r) >> 1;
        if(ql <= mid){
            range_opposite(lson(x) , ql , qr);
        }
        if(mid + 1 <= qr){
            range_opposite(rson(x) , ql , qr);
        }
        pushup(x);
    }

    int range_query(int x , int ql , int qr){
        if(ql <= node[x].l && node[x].r <= qr){
            return node[x].num;
        }
        pushdown(x);
        int mid = (node[x].l + node[x].r) >> 1 , ans = 0;
        if(ql <= mid){
            ans += range_query(lson(x) , ql , qr);
        }
        if(mid + 1 <= qr){
            ans += range_query(rson(x) , ql , qr);
        }
        return ans;
    }

    int range_max(int x , int ql , int qr){
        if(ql <= node[x].l && node[x].r <= qr){
            return node[x].maxn;
        }
        pushdown(x);
        int mid = (node[x].l + node[x].r) >> 1 , ans = -0x3f3f3f3f;
        if(ql <= mid){
            ans = max(ans , range_max(lson(x) , ql , qr));
        }
        if(mid + 1 <= qr){
            ans = max(ans , range_max(rson(x) , ql , qr));
        }
        return ans;
    }

    int range_min(int x , int ql , int qr){
        if(ql <= node[x].l && node[x].r <= qr){
            return node[x].minn;
        }
        pushdown(x);
        int mid = (node[x].l + node[x].r) >> 1 , ans = 0x3f3f3f3f;
        if(ql <= mid){
            ans = min(ans , range_min(lson(x) , ql , qr));
        }
        if(mid + 1 <= qr){
            ans = min(ans , range_min(rson(x) , ql , qr));
        }
        return ans;
    }

    #undef lson
    #undef rson
}

void tree_opposite(int x , int y){
    while(tp[x] != tp[y]){
        if(dep[tp[x]] < dep[tp[y]]){
            swap(x , y);
        }
        Segment_tree :: range_opposite(1 , dfn[tp[x]] , dfn[x]);
        x = fa[tp[x]];
    }
    if(x != y){
        if(dep[x] > dep[y]) swap(x , y);
        Segment_tree :: range_opposite(1 , dfn[x] + 1 , dfn[y]);
    }
}

int tree_query(int x , int y){
    int ans = 0;
    while(tp[x] != tp[y]){
        if(dep[tp[x]] < dep[tp[y]]){
            swap(x , y);
        }
        ans += Segment_tree :: range_query(1 , dfn[tp[x]] , dfn[x]);
        x = fa[tp[x]];
    }
    if(x != y){
        if(dep[x] > dep[y]) swap(x , y);
        ans += Segment_tree :: range_query(1 , dfn[x] + 1 , dfn[y]);
    }
    return ans;
}

int tree_max(int x , int y){
    int ans = -0x3f3f3f3f;
    while(tp[x] != tp[y]){
        if(dep[tp[x]] < dep[tp[y]]){
            swap(x , y);
        }
        ans = max(ans , Segment_tree :: range_max(1 , dfn[tp[x]] , dfn[x]));
        x = fa[tp[x]];
    }
    if(x != y){
        if(dep[x] > dep[y]) swap(x , y);
        ans = max(ans , Segment_tree :: range_max(1 , dfn[x] + 1 , dfn[y]));
    }
    return ans;
}

int tree_min(int x , int y){
    int ans = 0x3f3f3f3f;
    while(tp[x] != tp[y]){
        if(dep[tp[x]] < dep[tp[y]]){
            swap(x , y);
        }
        ans = min(ans , Segment_tree :: range_min(1 , dfn[tp[x]] , dfn[x]));
        x = fa[tp[x]];
    }
    if(x != y){
        if(dep[x] > dep[y]) swap(x , y);
        ans = min(ans , Segment_tree :: range_min(1 , dfn[x] + 1 , dfn[y]));    
    }
    return ans;
}

int from1[M] , to1[M];

void change(int x , int y , int val){
    if(dep[x] > dep[y]) swap(x , y);
    Segment_tree :: point_change(1 , dfn[y] , val);
}

int main() {
    #ifdef LOCAL
        freopen("P1505_4.in" , "r" , stdin);
        freopen("P1505_4.out" , "w" , stdout);
    #endif
    int n; scanf("%d" , &n);
    int u , v , d;
    rep(i , 1 , n - 1){
        scanf("%d%d%d" , &u , &v , &d);
        u ++; v ++;
        add_edge(u , v , d);
        from1[i] = u; to1[i] = v;
    }
    dfs1(1 , 0 , 1);
    dfs2(1 , 1);
    Segment_tree :: build(1 , 1 , n);

    int m; scanf("%d" , &m);
    char opt[10];
    int x , y;
    while(m --){
        scanf("%s" , opt);
        scanf("%d%d" , &x , &y);
        if(opt[0] == 'C'){
            change(from1[x] , to1[x] , y);
        }
        else if(opt[0] == 'N'){
            x ++; y ++;
            tree_opposite(x , y);
        }
        else if(opt[0] == 'S'){
            x ++; y ++;
            printf("%d\n" , tree_query(x , y));
        }
        else{
            if(opt[1] == 'A'){
                x ++ , y ++;
                printf("%d\n" , tree_max(x , y));
            }
            else if(opt[1] == 'I'){
                x ++ , y ++;
                printf("%d\n" , tree_min(x , y));
            }
        }
    }

    return 0;
}

---

THE END