题目地址：洛谷：【P2486】[SDOI2011]染色 – 洛谷、BZOJ：Problem 2243. — [SDOI2011]染色

题目描述

给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），
如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。

输入输出格式

输入格式：
第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。
下面 行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；
“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

输出格式：
对于每个询问操作，输出一行答案。

输入输出样例

输入样例#1：

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

输出样例#1：

3
1
2

说明

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

题解

树链信息自然就是树剖。线段树维护当前区间左右端颜色以及这段区间中间有几段。合并检查拼接点是否同样颜色。树剖上跳的过程类似，实现见代码。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'Q' || c == 'C';
}

inline char readop() {
    char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 100005;

int n, m, w[MAXN], ut, vt, at, bt, ct;
char op;
int fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], ptn[MAXN], top[MAXN], dep[MAXN], cnt;
std::vector<int> gra[MAXN];

inline void addedge(int u, int v) {
    gra[u].push_back(v);
    gra[v].push_back(u);
}

inline void dfs1(int u) {
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == fa[u]) continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs1(v);
        siz[u] += siz[v] + 1;
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

inline void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++cnt;
    ptn[dfn[u]] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

struct Node {
    int l, r, tot;
    bool tag;
} sgt[MAXN << 2];

inline void pushdown(int o, int l, int r) {
    int lch = o << 1, rch = (o << 1) | 1;
    if(sgt[o].tag) {
        sgt[lch].l = sgt[lch].r = sgt[rch].l = sgt[rch].r = sgt[o].l;
        sgt[lch].tag = sgt[rch].tag = true;
        sgt[lch].tot = sgt[rch].tot = 1;
        sgt[o].tag = false;
    }
}

inline void merge(Node &rt, Node ls, Node rs) {
    rt.l = ls.l;
    rt.r = rs.r;
    rt.tot = ls.tot + rs.tot;
    if(ls.r == rs.l) rt.tot--;
}

inline void build(int o, int l, int r) {
    if(l == r) {
        sgt[o].l = sgt[o].r = w[ptn[l]];
        sgt[o].tot = 1;
        return;
    }
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    build(lch, l, mid);
    build(rch, mid + 1, r);
    merge(sgt[o], sgt[lch], sgt[rch]);
}

inline void modify(int o, int l, int r, int ll, int rr, int v) {
    if(l == ll && r == rr) {
        sgt[o].l = sgt[o].r = v;
        sgt[o].tot = 1;
        sgt[o].tag = true;
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(rr <= mid) {
        modify(lch, l, mid, ll, rr, v);
    } else if(ll > mid) {
        modify(rch, mid + 1, r, ll, rr, v);
    } else {
        modify(lch, l, mid, ll, mid, v);
        modify(rch, mid + 1, r, mid + 1, rr, v);
    }
    merge(sgt[o], sgt[lch], sgt[rch]);
}

inline Node query(int o, int l, int r, int ll, int rr) {
    if(l == ll && r == rr) {
        return sgt[o];
    }
    pushdown(o, l, r);
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(rr <= mid) {
        return query(lch, l, mid, ll, rr);
    } else if(ll > mid) {
        return query(rch, mid + 1, r, ll, rr);
    } else {
        Node ls = query(lch, l, mid, ll, mid), rs = query(rch, mid + 1, r, mid + 1, rr), res;
        merge(res, ls, rs);
        return res;
    }
}

inline void modify(int u, int v, int c) {
    int tu = top[u], tv = top[v];
    while(tu != tv) {
        if(dep[tu] > dep[tv]) {
            std::swap(tu, tv);
            std::swap(u, v);
        }
        modify(1, 1, n, dfn[tv], dfn[v], c);
        v = fa[tv];
        tv = top[v];
    }
    if(dep[u] > dep[v]) std::swap(u, v);
    modify(1, 1, n, dfn[u], dfn[v], c);
}

inline int query(int u, int v) {
    Node t;
    int res = 0, cu = -1, cv = -1, tu = top[u], tv = top[v];
    while(tu != tv) {
        if(dep[tu] > dep[tv]) {
            std::swap(tu, tv);
            std::swap(u, v);
            std::swap(cu, cv);
        }
        t = query(1, 1, n, dfn[tv], dfn[v]);
        res += t.tot;
        if(t.r == cv) res--;
        cv = t.l;
        v = fa[tv];
        tv = top[v];
    }
    if(dep[u] > dep[v]) {
        std::swap(u, v);
        std::swap(cu, cv); 
    }
    t = query(1, 1, n, dfn[u], dfn[v]);
    res += t.tot;
    if(t.l == cu) res--;
    if(t.r == cv) res--;
    return res;
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) w[i] = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        addedge(ut, vt);
    }
    dfs1(1);
    dfs2(1, 1);
    build(1, 1, n);
    while(m--) {
        op = readop();
        at = readint();
        bt = readint();
        if(op == 'Q') {
            printf("%d\n", query(at, bt));
        }
        if(op == 'C') {
            ct = readint();
            modify(at, bt, ct);
        }
    }
    return 0;
}