List wants to travel
題意:
給一棵樹,每條邊有個顔色,兩種操作:
- Change a b c,把a到b的簡單路徑的邊顔色變成c
- Query a b,查詢a到b的簡單路徑有多少段顔色,連續相鄰的同色邊算一段。
思路:
先建立樹剖然後用線段樹維護,記錄一個區間内的顔色段數,最左顔色和最右顔色,然後就可以區間合并了,需要注意合并的順序,沒想清楚很容易就wa了,我想的是總是按查詢的時間順序把區間挨個接起來,最後合并兩邊鍊的時候反轉一個區間,接在另一個後面。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
const int NO = -;
const int N = ;
vector<int>G[N];
int sav[N][];
int dep[N], fa[N], son[N], sz[N];
void dfs1(int rt) {
sz[rt] = ;
for(int k = ; k < G[rt].size(); ++k) {
int v = G[rt][k];
if(v == fa[rt]) continue;
dep[v] = dep[rt]+;
fa[v] = rt;
dfs1(v);
sz[rt] += sz[v];
if(son[rt] == || sz[son[rt]] < sz[v]) son[rt] = v;
}
}
int w[N], atw[N], top[N], wcnt;
void dfs2(int rt, int tp) {
w[rt] = ++wcnt, atw[wcnt] = rt;
top[rt] = tp;
if(son[rt]) dfs2(son[rt], tp);
for(int k = ; k < G[rt].size(); ++k) {
int v = G[rt][k];
if(v == fa[rt] || v == son[rt]) continue;
dfs2(v, v);
}
}
struct node{
int sum, l, r;
node(){ sum = , l = NO, r = NO; }
node operator + (const node& z) {
node res;
if(r == NO && z.l == NO) return res;
if(r == NO && z.l != NO) return z;
else if(r != NO && z.l == NO) return *this;
res.sum = sum+z.sum;
if(r == z.l) res.sum--;
res.l = l, res.r = z.r;
return res;
}
}tree[N<<];
int lazy[N<<];
inline void push_down(int rt) {
if(lazy[rt] != NO) {
tree[rt<<].sum = tree[rt<<|].sum = ;
tree[rt<<].l = tree[rt<<].r = lazy[rt];
tree[rt<<|].l = tree[rt<<|].r = lazy[rt];
lazy[rt<<] = lazy[rt<<|] = lazy[rt];
lazy[rt] = NO;
}
}
void update(int rt, int l, int r, int ql, int qr, int v) {
if(ql <= l && qr >= r) {
tree[rt].sum = ;
tree[rt].l = tree[rt].r = v;
lazy[rt] = v;
return;
}
push_down(rt);
int mid = (l+r) >> ;
if(ql <= mid) update(rt<<, l, mid, ql, qr, v);
if(qr > mid) update(rt<<|, mid+, r, ql, qr, v);
tree[rt] = tree[rt<<] + tree[rt<<|];
}
node query(int rt, int l, int r, int ql, int qr) {
if(ql <= l && qr >= r) {
return tree[rt];
}
push_down(rt);
node res; int mid = (l+r) >> ;
if(ql <= mid){
res = res+query(rt<<, l, mid, ql, qr);
}
if(qr > mid){
res = res+query(rt<<|, mid+, r, ql, qr);
}
tree[rt] = tree[rt<<] + tree[rt<<|];
return res;
}
int query(int va, int vb) {
int f1 = top[va], f2 = top[vb];
node a, b;
while(f1 != f2) {
if(dep[f1] > dep[f2]) {
a = query(, , wcnt, w[f1], w[va])+a;
va = fa[f1], f1 = top[va];
}
else{
b = query(, , wcnt, w[f2], w[vb])+b;
vb = fa[f2], f2 = top[vb];
}
}
if(va == vb){
swap(b.l, b.r);
a = b+a;
return a.sum;
}
if(dep[va] < dep[vb]) {
b = query(, , wcnt, w[son[va]], w[vb])+b;
swap(b.l, b.r);
a = b+a;
return a.sum;
}
else {
a = query(, , wcnt, w[son[vb]], w[va])+a;
swap(b.l, b.r);
a = b+a;
return a.sum;
}
}
void update(int va, int vb, int v) {
int f1 = top[va], f2 = top[vb];
while(f1 != f2) {
if(dep[f1] < dep[f2]){
swap(f1, f2);
swap(va, vb);
}
update(, , wcnt, w[f1], w[va], v);
va = fa[f1], f1 = top[va];
}
if(va == vb) return;
if(dep[va] < dep[vb]) swap(va, vb);
update(, , wcnt, w[son[vb]], w[va], v);
}
char s[];
int main() {
int n, m;
while(scanf("%d%d", &n, &m) != EOF) {
for(int i = ; i <= n; ++i) G[i].clear();
for(int a, b, c, i = ; i < n; ++i) {
scanf("%d%d%d", &a, &b, &c);
G[a].push_back(b);
G[b].push_back(a);
sav[i][] = a, sav[i][] = b, sav[i][] = c;
}
memset(son, , sizeof(son));
fa[] = , dep[] = ;
dfs1(); wcnt = ;
dfs2(, );
for(int i = ; i <= wcnt; ++i) {
tree[i].sum = ;
tree[i].l = tree[i].r = NO;
lazy[i] = NO;
}
for(int i = ; i < n; ++i) {
if(dep[sav[i][]] > dep[sav[i][]]) swap(sav[i][], sav[i][]);
update(, , wcnt, w[sav[i][]], w[sav[i][]], sav[i][]);
}
while(m--) {
scanf("%s", s);
if(s[] == 'Q') {
int l, r;
scanf("%d%d", &l, &r);
if(l == r) { puts("0"); continue; }
printf("%d\n", query(l, r));
}
else if(s[] == 'C') {
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
update(l, r, v);
}
}
}
return ;
}