边权化点权

• 题目描述
• 题目链接
• 解析
• 代码
• 测试样例

题目描述

给定一棵树，支持如下操作

1. CHANGE i t 把第 i 条边的边权变成 t
2. QUERY a b 输出从 a到 b的路径上最大的边权。当
   a = b时，输出 0

题目链接

传送门

解析

和上一篇博客的方法一样，而且本题只涉及一个懒标签，细节和代码量都更少，附上上一篇的链接
树链剖分03

代码

#include <algorithm>
#include <cstdio>
#include <cctype>
#define mid (l + r >> 1)
using namespace std;
const int N = 1e5 + 10;
int n, tot, cnt;
int head[N];
int dep[N], size[N], par[N], son[N], w[N];
int top[N], dfn[N], pre[N];
struct edge{
    int to, nxt, val;
}e[N << 1];

inline int read(){
    int x = 0, op = 1;
    char ch = getchar();
    while (!isdigit(ch)){
        if (ch == '-') op = -1;
        ch = getchar();
    }
    while (isdigit(ch)){
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * op;
}

inline void add_edge(int u, int v, int w){
    e[++tot] = {v, head[u], w};
    head[u] = tot;
}

inline void dfs1(int u, int fa){
    size[u] = 1;
    par[u] = fa;
    dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa) continue;
        w[v] = e[i].val;
        dfs1(v, u);
        size[u] += size[v];
        if (size[v] > size[son[u]])
            son[u] = v;
    }
}

inline void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++cnt;
    pre[cnt] = u;
    if (son[u])
        dfs2(son[u], tp);
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v != par[u] && v != son[u])
            dfs2(v, v);
    }
}

int Max[N << 2], tag[N << 2];
inline void push_up(int i){
    Max[i] = max(Max[i << 1], Max[i << 1|1]);
}

inline void push_down(int i){
    if (tag[i] == -1) return;
    Max[i << 1] = tag[i];
    Max[i << 1|1] = tag[i];
    tag[i << 1] = tag[i];
    tag[i << 1|1] = tag[i];
    tag[i] = -1;
}

inline void buildTree(int i, int l, int r ){
    tag[i] = -1;
    if(l == r){
        Max[i] = w[pre[l]];
        return;
    }
    buildTree(i << 1, l, mid);
    buildTree(i << 1|1, mid + 1, r);
    push_up(i);
}

inline void modify_point(int i, int l, int r, int pos, int val){
    if (l == r){
        Max[i] = val;
        tag[i] = val;
        return;
    }

    push_down(i);
    if (pos <= mid)
        modify_point(i << 1, l, mid, pos, val);
    else
        modify_point(i << 1|1, mid + 1, r, pos, val);
    push_up(i);
}

inline int query_interval(int i, int l, int r, int crtl, int crtr){
    if (l > crtr || r < crtl)
        return 0;
    if (l >= crtl && r <= crtr)
        return Max[i];

    int res = 0;
    if (mid >= crtl)
        res = max(res, query_interval(i << 1, l, mid, crtl, crtr));
    if (mid < crtr)
        res = max(res, query_interval(i << 1|1, mid + 1, r, crtl, crtr));
    return res;
}

inline int tree_max(int u, int v){
    int res = 0;
    while (top[u] != top[v]){
        if (dep[top[u]] < dep[top[v]])
            swap(u, v);
        res = max(res, query_interval(1, 1, n, dfn[top[u]], dfn[u]));
        u = par[top[u]];
    }

    if (dep[u] > dep[v])
        swap(u, v);
    res = max(res, query_interval(1, 1, n, dfn[u] + 1, dfn[v]));
    return res;
}

int main() {
    n = read();
    for (int i = 1, x, y, z; i <= n - 1 ; ++i) {
        x = read(), y = read(), z = read();
        add_edge(x, y, z), add_edge(y, x, z);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    buildTree(1, 1, n);
    char opt[8] = {0};
    int u = 0, v = 0;
    while (true){
        scanf("%s", opt);
        if (opt[0] == 'D')
            break;

        u = read(), v = read();
        if(opt[0] == 'C'){
            int a = e[u * 2].to;
            int b = e[u * 2 - 1].to;
            int x = dfn[a] > dfn[b] ? a : b;
            modify_point(1, 1, n, dfn[x], v);
        }else{
            printf("%d\n", u == v ? 0 : tree_max(u, v));
        }
    }
    return 0;
}

测试样例

/*
input:
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
output:
1
3
*/