[SDOI 2011]染色

时间：2023-03-10 01:09:02
[SDOI 2011]染色

Description

题库链接

给定一棵有 \(n\) 个节点的无根树和 \(m\) 个操作，操作有 \(2\) 类：

  1. 将节点 \(a\) 到节点 \(b\) 路径上所有点都染成颜色 \(c\) ；
  2. 询问节点 \(a\) 到节点 \(b\) 路径上的颜色段数量（连续相同颜色被认为是同一段）

Solution

线段树苟题。因为没有下传 \(lazy\) 标记调了一上午。

Code

//It is made by Awson on 2018.3.4

#include <bits/stdc++.h>

#define LL long long

#define dob complex<double>

#define Abs(a) ((a) < 0 ? (-(a)) : (a))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

#define writeln(x) (write(x), putchar('\n'))

#define lowbit(x) ((x)&(-(x)))

using namespace std;

const int N = 1e5;

void read(int &x) {

    char ch; bool flag = 0;

    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());

    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());

    x *= 1-2*flag;

}

void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }

void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }

int n, m, c[N+5], a[N+5], u, v, ca;

struct tt {int to, next; }edge[(N<<1)+5];

int path[N+5], Top;

int size[N+5], id[N+5], son[N+5], top[N+5], dep[N+5], fa[N+5], pos;

char ch[5];

struct node {

    int l, r, cnt;

    node() {}

    node(int _l, int _r, int _cnt) {l = _l, r = _r, cnt = _cnt; }

    node operator + (const node &b) const {node tmp; tmp.l = l, tmp.r = b.r, tmp.cnt = cnt+b.cnt-(r==b.l); return tmp; }

};

struct Segment_tree {

#define lr(o) (o<<1)

#define rr(o) (o<<1|1)

    node sgm[(N<<2)+5]; int lazy[(N<<2)+5];

    void pushdown(int o) {sgm[lr(o)] = sgm[rr(o)] = sgm[o]; lazy[lr(o)] = lazy[rr(o)] = 1; lazy[o] = 0; }

    void build(int o, int l, int r) {

    if (l == r) {sgm[o] = node(a[l], a[l], 1); return; }

    int mid = (l+r)>>1;

    build(lr(o), l, mid); build(rr(o), mid+1, r); sgm[o] = sgm[lr(o)]+sgm[rr(o)];

    }

    node query(int o, int l, int r, int a, int b) {

    if (a <= l && r <= b) return sgm[o];

    if (lazy[o]) pushdown(o); int mid = (l+r)>>1;

    if (b <= mid) return query(lr(o), l, mid, a, b);

    if (a > mid) return query(rr(o), mid+1, r, a, b);

    return query(lr(o), l, mid, a, b)+query(rr(o), mid+1, r, a, b);

    }

    void update(int o, int l, int r, int a, int b, int col) {

    if (a <= l && r <= b) {sgm[o] = node(col, col, 1), lazy[o] = 1; return; }

    if (lazy[o]) pushdown(o); int mid = (l+r)>>1;

    if (a <= mid) update(lr(o), l, mid, a, b, col);

    if (b > mid) update(rr(o), mid+1, r, a, b, col);

    sgm[o] = sgm[lr(o)]+sgm[rr(o)];

    }

}T;

void add(int u, int v) {edge[++Top].to = v, edge[Top].next = path[u], path[u] = Top; }

void dfs1(int o, int depth, int father) {

    dep[o] = depth, size[o] = 1, fa[o] = father;

    for (int i = path[o]; i; i = edge[i].next)

    if (dep[edge[i].to] == 0) {

        dfs1(edge[i].to, depth+1, o); size[o] += size[edge[i].to];

        if (size[edge[i].to] > size[son[o]]) son[o] = edge[i].to;

    }

}

void dfs2(int o, int tp) {

    id[o] = ++pos, a[pos] = c[o], top[o] = tp;

    if (son[o]) dfs2(son[o], tp);

    for (int i = path[o]; i; i = edge[i].next)

    if (edge[i].to != fa[o] && edge[i].to != son[o]) dfs2(edge[i].to, edge[i].to);

}

void update(int u, int v, int c) {

    while (top[u] != top[v]) {

    if (dep[top[u]] < dep[top[v]]) Swap(u, v);

    T.update(1, 1, n, id[top[u]], id[u], c);

    u = fa[top[u]];

    }

    if (dep[u] < dep[v]) Swap(u, v);

    T.update(1, 1, n, id[v], id[u], c);

}

int query(int u, int v) {

    node n1, n2; int f1 = 1, f2 = 1;

    while (top[u] != top[v]) {

    if (dep[top[u]] > dep[top[v]]) {

        if (f1) n1 = T.query(1, 1, n, id[top[u]], id[u]);

        else n1 = T.query(1, 1, n, id[top[u]], id[u])+n1;

        u = fa[top[u]]; f1 = 0;

    }else {

        if (f2) n2 = T.query(1, 1, n, id[top[v]], id[v]);

        else n2 = T.query(1, 1, n, id[top[v]], id[v])+n2;

        v = fa[top[v]]; f2 = 0;

    }

    }

    if (dep[u] > dep[v]) {

    if (f1) n1 = T.query(1, 1, n, id[v], id[u]);

    else n1 = T.query(1, 1, n, id[v], id[u])+n1; f1 = 0;

    }else {

    if (f2) n2 = T.query(1, 1, n, id[u], id[v]);

    else n2 = T.query(1, 1, n, id[u], id[v])+n2; f2 = 0;

    }

    if (f1) return n2.cnt;

    if (f2) return n1.cnt;

    Swap(n1.l, n1.r); n1 = n1+n2; return n1.cnt;

}

void work() {

    read(n), read(m); for (int i = 1; i <= n; i++) read(c[i]);

    for (int i = 1; i < n; i++) read(u), read(v), add(u, v), add(v, u);

    dfs1(1, 1, 0), dfs2(1, 1); T.build(1, 1, n);

    while (m--) {

    scanf("%s", ch);

    if (ch[0] == 'Q') read(u), read(v), writeln(query(u, v));

    else read(u), read(v), read(ca), update(u, v, ca);

    }

}

int main() {

    work(); return 0;

}

相关文章