Luogu [SDOI2014]旅行

题解

题记

最近做题第一道写完代码直接过样例，然后A掉的,唉

题意

一棵树
每个节点有各自的属性(相同数字代表相同属性)和权值
4中操作
修改节点的属性
修改节点的权值
询问一条路径中所有与起点属性相同的点的价值之和
询问一条路径中所有与起点属性相同的点的最大权职

解

树上问题转化到链上
当然是树链剖分啦
但是属性不同怎么办
那我们就对每个属性都开一颗线段树
查询时只需找到对应属性的线段树进行查询就可以啦
对每个属性都开线段树？？？
空间爆炸
我们可以动态开点
(其实这题主要是练一下线段树的动态开点)
这样就可以完美的过掉这道T啦

Code

#include <bits/stdc++.h>
const int N = 1e5 + 10;
#define gc getchar()
int n, T;
int bel[N], data[N], root[N];
int size[N], son[N], topp[N], fa[N], deep[N], tree[N], bef[N], Tree;
int tot, W[N * 20], Max[N * 20], lson[N * 20], rson[N * 20];
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
struct Node {int v, nxt;} G[N << 2];
int now = 1, head[N];
inline void Add(int u, int v) {G[now].v = v; G[now].nxt = head[u]; head[u] = now ++;}
void Dfs_1(int u, int f_, int dep) {
    fa[u] = f_; deep[u] = dep; size[u] = 1;
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(v != f_) {
            Dfs_1(v, u, dep + 1);
            size[u] += size[v];
            if(size[son[u]] < size[v]) son[u] = v;
        }
    }
}
void Dfs_2(int u, int tp) {
    topp[u] = tp; tree[u] = ++ Tree; bef[Tree] = u;
    if(!son[u]) return ;
    Dfs_2(son[u], tp);
    for(int i = head[u]; ~ i; i = G[i].nxt) {
        int v = G[i].v;
        if(v != fa[u] && v != son[u]) Dfs_2(v, v);
    }
}
void Poi_G(int l, int r, int & jd, int x, int w) {
    if(!jd) jd = ++ tot;
    W[jd] += w;
    if(l == r) {Max[jd] += w; return ;}
    int mid = (l + r) >> 1;
    if(x <= mid) Poi_G(l, mid, lson[jd], x, w);
    else Poi_G(mid + 1, r, rson[jd], x, w);
    Max[jd] = std:: max(Max[lson[jd]], Max[rson[jd]]);
}
int Ans;
void Sec_A_sum(int l, int r, int jd, int x, int y) {
    if(! jd) return ;
    if(x <= l && r <= y) {Ans += W[jd]; return ;}
    int mid = (l + r) >> 1;
    if(x <= mid) Sec_A_sum(l, mid, lson[jd], x, y);
    if(y > mid ) Sec_A_sum(mid + 1, r, rson[jd], x, y);
}
void Sec_A_max(int l, int r, int jd, int x, int y) {
    if(! jd) return ;
    if(x <= l && r <= y) {Ans = std:: max(Ans, Max[jd]); return ;}
    int mid = (l + r) >> 1;
    if(x <= mid) Sec_A_max(l, mid, lson[jd], x, y);
    if(y > mid ) Sec_A_max(mid + 1, r, rson[jd], x, y);
}
inline int Sec_A_Imp(int x, int y, int Rt) {
    int tp1 = topp[x], tp2 = topp[y], ret(0);
    while(tp1 != tp2) {
        if(deep[tp1] < deep[tp2]) std:: swap(tp1, tp2), std:: swap(x, y);
        Ans = 0;
        Sec_A_sum(1, n, root[Rt], tree[tp1], tree[x]);
        ret += Ans;
        x = fa[tp1];
        tp1 = topp[x];
    }
    Ans = 0;
    if(deep[x] < deep[y]) std:: swap(x, y);
    Sec_A_sum(1, n, root[Rt], tree[y], tree[x]);
    ret += Ans;
    return ret;
}
inline int Sec_A_Imp2(int x, int y, int Rt) {
    int tp1 = topp[x], tp2 = topp[y]; Ans = 0;
    while(tp1 != tp2) {
        if(deep[tp1] < deep[tp2]) std:: swap(tp1, tp2), std:: swap(x, y);
        Sec_A_max(1, n, root[Rt], tree[tp1], tree[x]);
        x = fa[tp1];
        tp1 = topp[x];
    }
    if(deep[x] < deep[y]) std:: swap(x, y);
    Sec_A_max(1, n, root[Rt], tree[y], tree[x]);
    return Ans;
}
int main() {
    n = read(); T = read();
    for(int i = 1; i <= n; i ++) data[i] = read(), bel[i] = read();
    for(int i = 1; i <= n; i ++) head[i] = -1;
    for(int i = 1; i <  n; i ++) {
        int a = read(), b = read();
        Add(a, b); Add(b, a);
    }
    Dfs_1(1, 0, 1);
    Dfs_2(1, 1);
    for(int i = 1; i <= n; i ++) Poi_G(1, n, root[bel[i]], tree[i], data[i]);
    while(T --) {
        std:: string opt; std:: cin >> opt;
        int x = read(), y = read();
        if(opt == "CC") Poi_G(1, n, root[bel[x]], tree[x], -data[x]),
                        Poi_G(1, n, root[y], tree[x], data[x]), bel[x] = y;
        else if(opt == "CW") Poi_G(1, n, root[bel[x]], tree[x], y - data[x]), data[x] = y;
        else if(opt == "QS") std:: cout << Sec_A_Imp(x, y, bel[x]) << "\n";
        else std:: cout << Sec_A_Imp2(x, y, bel[x]) << "\n";
    }
    return 0;
}