初見安~最近要到CSP了是以沒時間寫部落格QuQ
這裡是傳送門：洛谷P2486 染色
題解
很明顯是一個樹鍊剖分的裸題——并且需要借助線段樹。我們考慮如何用線段樹維護區間内的顔色數資訊。
我們可以定義一個flag，表示有flag的區間内的所有點都是flag這個顔色。比如，有線段樹上的區間點
，我們先把
賦成顔色1，後來又給
賦上顔色2，那麼我們最後隻認在區間
的标記即可。如果順序反過來，我們在找區間
的時候就可以把沿路的标記down下去。當然，多個顔色flag就是0.
加上樹剖，我們還需要管的就是：如果兩個區間分别有a個色段和b個色段，但是拼合起來的時候兩端顔色相同，怎麼處理？其實我們在樹剖網上跳的時候順手查一下單點的值，也就是看鍊頭和鍊頭的父親的顔色是否相同即可，相同則
，否則
。
沒有了。【？？？？
其實真的是個很闆子的題目……也就是對于區間的拼合的時候特判的處理比較麻煩。
線段樹要處理的值：左端點顔色，右端點顔色，區間段數，flag
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 100005
using namespace std;
typedef long long ll;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
int n, m, val[maxn];
struct edge {int to, nxt;} e[maxn << 1];
int head[maxn], k = 0;
void add(int u, int v) {e[k] = {v, head[u]}; head[u] = k++;}
int size[maxn], dep[maxn], son[maxn], fa[maxn], top[maxn], dfn[maxn], raw[maxn], tot = 0;
void dfs1(int u) {
size[u] = 1; register int v;
for(int i = head[u]; ~i; i = e[i].nxt) {
v = e[i].to; if(v == fa[u]) continue;
fa[v] = u, dep[v] = dep[u] + 1;
dfs1(v); size[u] += size[v];
if(size[son[u]] < size[v]) son[u] = v;
}
}
void dfs2(int u, int tp) {
top[u] = tp, dfn[u] = ++tot; raw[tot] = u;
if(son[u]) dfs2(son[u], tp); register int v;
for(int i = head[u]; ~i; i = e[i].nxt) {
v = e[i].to; if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
struct node {
int lc, rc, cnt, flag;
}tree[maxn << 2];
void build(int p, int l, int r) {
if(l == r) {tree[p].lc = tree[p].rc = val[raw[l]], tree[p].cnt = 1; return;}
int mid = l + r >> 1;
build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
tree[p].cnt = tree[p << 1].cnt + tree[p << 1 | 1].cnt;
if(tree[p << 1].rc == tree[p << 1 | 1].lc) tree[p].cnt--;//lc和rc就是左右端點的顔色
tree[p].lc = tree[p << 1].lc, tree[p].rc = tree[p << 1 | 1].rc;
}
void down(int p, int l, int r) {//下傳标記
tree[p << 1].lc = tree[p << 1 | 1].lc = tree[p << 1].rc = tree[p << 1 | 1].rc = tree[p].flag;
tree[p << 1].flag = tree[p << 1 | 1].flag = tree[p].flag;
tree[p << 1].cnt = tree[p << 1 | 1].cnt = 1;
tree[p].flag = 0;
}
int ask(int p, int l, int r, int ls, int rs) {
if(ls <= l && r <= rs) return tree[p].cnt;
int mid = l + r >> 1;
if(tree[p].flag) down(p, l, r);
if(rs <= mid) return ask(p << 1, l, mid, ls, rs);
else if(ls > mid) return ask(p << 1 | 1, mid + 1, r, ls, rs);
else return ask(p << 1, l, mid, ls, rs) + ask(p << 1 | 1, mid + 1, r, ls, rs) - (tree[p << 1].cnt + tree[p << 1 | 1].cnt == tree[p].cnt? 0 : 1);//這裡也是看有沒有拼合區間
}
int quary(int p, int l, int r, int x) {//單點查詢，本來可以和區間查詢放到一起用……
if(tree[p].flag) return tree[p].flag;
if(l == r) return tree[p].lc;
int mid = l + r >> 1;
if(x <= mid) return quary(p << 1, l, mid, x);
else return quary(p << 1 | 1, mid + 1, r, x);
}
void ask_path(int u, int v) {
int ans = 0;
while(top[u] != top[v]) {
if(dep[top[u]] > dep[top[v]]) swap(u, v);
ans += ask(1, 1, n, dfn[top[v]], dfn[v]);
if(quary(1, 1, n, dfn[top[v]]) == quary(1, 1, n, dfn[fa[top[v]]])) ans--;//看是否端點顔色相同
v = fa[top[v]];
}
if(dep[u] > dep[v]) swap(u, v);
ans += ask(1, 1, n, dfn[u], dfn[v]);
printf("%d\n", ans);
}
void change(int p, int l, int r, int ls, int rs, int c) {
if(ls <= l && r <= rs) {tree[p].flag = tree[p].lc = tree[p].rc = c; tree[p].cnt = 1; return;}
int mid = l + r >> 1;
if(tree[p].flag) down(p, l, r);
if(ls <= mid) change(p << 1, l, mid, ls, rs, c);
if(rs > mid) change(p << 1 | 1, mid + 1, r, ls, rs, c);
tree[p].cnt = tree[p << 1].cnt + tree[p << 1 | 1].cnt;
if(tree[p << 1].rc == tree[p << 1 | 1].lc) tree[p].cnt--;
tree[p].lc = tree[p << 1].lc, tree[p].rc = tree[p << 1 | 1].rc;
}
void change_path(int u, int v, int c) {
while(top[u] != top[v]) {
if(dep[top[u]] > dep[top[v]]) swap(u, v);
change(1, 1, n, dfn[top[v]], dfn[v], c);
v = fa[top[v]];
}
if(dep[u] > dep[v]) swap(u, v);
change(1, 1, n, dfn[u], dfn[v], c);
}
signed main() {
memset(head, -1, sizeof head);
n = read(), m = read();
register int u, v, color;
for(int i = 1; i <= n; i++) val[i] = read();
for(int i = 1; i < n; i++) u = read(), v = read(), add(u, v), add(v, u);
dfs1(1); dfs2(1, 1);
build(1, 1, n);
char op;
while(m--) {
cin >> op; u = read(), v = read();
if(op == 'Q') ask_path(u, v);
else color = read(), change_path(u, v, color);
}
return 0;
}
就這樣了。
迎評：）
——End——