旅行

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 4096 字
树上每城有信仰c与评级w；支持改信仰CC、改
一本通
练习
正文

/*
原题：T1564 「一本通 4.5 练习 4」旅行（SDOI2014）
题意：树上每城有信仰 c 与评级 w；支持改信仰 CC、改评级 CW、查询同信仰路径评级和 QS / 最大值 QM。
思路：按信仰建立动态开点线段树，下标为 HLD 的 dfn 序。dfn[x] 处只在“信仰 c 的树”里存评级 w。
改信仰：旧树该位清零、新树写入；改评级：在当前信仰树改该位。
路径查询沿 HLD 拆成 O(log n) 段，对目标信仰的线段树做区间求和/最大值。
复杂度：时间 O((N+Q)log^2 N)，空间 O((N+Q)log N)。
易错点：查询只对“两端信仰相同”的路径有效（端点保证相同）；
不同信仰城市在对应树中存 0（最大值用 0 不影响正评级）；动态开点注意用下标而非引用避免重分配失效。
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXC = 100005;
int n, q;
vector<int> g[MAXN];
int val[MAXN], belief[MAXN];
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rk[MAXN], tim;
void dfs1(int u, int p){
    fa[u] = p;
    dep[u] = dep[p] + 1;
    sz[u] = 1;
    son[u] = 0;
    for(int v : g[u]){
        if(v == p) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++tim;
    rk[tim] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int v : g[u]){
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
struct DynSeg {
    struct Node {
        int l, r;
        long long sum;
        int mx;
    };
    vector<Node> t;
    DynSeg(){
        t.push_back({0, 0, 0, 0});
    }
    int newnode(){
        t.push_back({0, 0, 0, 0});
        return (int)t.size() - 1;
    }
    int update(int o, int l, int r, int p, int v){
        if(!o) o = newnode();
        if(l == r){
            t[o].sum = v;
            t[o].mx = v;
            return o;
        }
        int mid = (l + r) / 2;
        if(p <= mid) t[o].l = update(t[o].l, l, mid, p, v);
        else t[o].r = update(t[o].r, mid + 1, r, p, v);
        t[o].sum = t[t[o].l].sum + t[t[o].r].sum;
        t[o].mx = max(t[t[o].l].mx, t[t[o].r].mx);
        return o;
    }
    pair<long long, int> query(int o, int l, int r, int ql, int qr){
        if(!o || ql > r || qr < l) return {0, 0};
        if(ql <= l && r <= qr) return {t[o].sum, t[o].mx};
        int mid = (l + r) / 2;
        auto L = query(t[o].l, l, mid, ql, qr);
        auto R = query(t[o].r, mid + 1, r, ql, qr);
        return {L.first + R.first, max(L.second, R.second)};
    }
};
DynSeg ds;
int root[MAXC];
long long path_query_sum(int u, int v, int c){
    long long res = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        res += ds.query(root[c], 1, n, dfn[top[u]], dfn[u]).first;
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    res += ds.query(root[c], 1, n, dfn[u], dfn[v]).first;
    return res;
}
int path_query_max(int u, int v, int c){
    int res = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        res = max(res, ds.query(root[c], 1, n, dfn[top[u]], dfn[u]).second);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    res = max(res, ds.query(root[c], 1, n, dfn[u], dfn[v]).second);
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> val[i] >> belief[i];
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i = 1; i <= n; i++){
        root[belief[i]] = ds.update(root[belief[i]], 1, n, dfn[i], val[i]);
    }
    while(q--){
        string op;
        cin >> op;
        if(op == "CC"){
            int x, c;
            cin >> x >> c;
            root[belief[x]] = ds.update(root[belief[x]], 1, n, dfn[x], 0);
            belief[x] = c;
            root[c] = ds.update(root[c], 1, n, dfn[x], val[x]);
        } else if(op == "CW"){
            int x, w;
            cin >> x >> w;
            val[x] = w;
            root[belief[x]] = ds.update(root[belief[x]], 1, n, dfn[x], w);
        } else if(op == "QS"){
            int x, y;
            cin >> x >> y;
            cout << path_query_sum(x, y, belief[x]) << "\n";
        }else{
            int x, y;
            cin >> x >> y;
            cout << path_query_max(x, y, belief[x]) << "\n";
        }
    }
    return 0;
}
旅行

正文

一本通·提高篇的其它内容
