涪陵做网站百度推广的几种方式

Description

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

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），

如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

Input

第一行包含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）路径上的颜色段数量。

Output

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

Sample Input

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

Sample Output

3
1
2

HINT

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

Source

第一轮day1

---

裸的树链剖分，计算答案的时候注意判断一下两条链相邻的两个颜色是否一样，如果一样就减一。

线段树的pushup同理。

---

#include <iostream>
#include <cstdio>
using namespace std;
#define reg register
inline int read() {int res = 0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48), ch=getchar();return res;
}
#define N 100005
int n, m;
struct edge {int nxt, to;
}ed[N*2];
int head[N], cnt;
inline void add(int x, int y) {ed[++cnt] = (edge){head[x], y};head[x] = cnt;
}int a[N];
int siz[N], fa[N], dep[N], top[N];
int id[N], rnk[N], son[N];void dfs(int x, int fe)
{siz[x] = 1, fa[x] = fe, dep[x] = dep[fe] + 1;for (reg int i = head[x] ; i ; i = ed[i].nxt){int to = ed[i].to;if (to == fe) continue;dfs(to, x);siz[x] += siz[to];if (siz[to] > siz[son[x]]) son[x] = to;}
}void efs(int x, int tep)
{top[x] = tep, id[x] = ++cnt, rnk[cnt] = x;if (son[x]) efs(son[x], tep);for (reg int i = head[x] ; i ; i = ed[i].nxt){int to = ed[i].to;if (to == fa[x] or to == son[x]) continue;efs(to, to);}
}struct SegMent {int lc, rc, dat, lazy;
}tr[N<<2];
#define ls(o) o << 1
#define rs(o) o << 1 | 1
#define lc(o) tr[o].lc
#define rc(o) tr[o].rc
#define dat(o) tr[o].dat
#define lazy(o) tr[o].lazyinline void pushup(int o)
{if (rc(ls(o)) == lc(rs(o))) dat(o) = dat(ls(o)) + dat(rs(o)) - 1;else dat(o) = dat(ls(o)) + dat(rs(o));lc(o) = lc(ls(o)), rc(o) = rc(rs(o));
}void Build(int l, int r, int o)
{if (l == r) {lc(o) = a[rnk[l]];rc(o) = a[rnk[l]];dat(o) = 1;lazy(o) = 0;return ;}int mid = l + r >> 1;Build(l, mid, ls(o));Build(mid + 1, r, rs(o));pushup(o);
}inline void pushdown(int o)
{if (!lazy(o)) return ;int c = lazy(o);lc(ls(o)) = c, rc(ls(o)) = c;dat(ls(o)) = 1, lazy(ls(o)) = c;lc(rs(o)) = c, rc(rs(o)) = c;dat(rs(o)) = 1, lazy(rs(o)) = c;lazy(o) = 0;
}void change(int l, int r, int o, int ql, int qr, int c)
{if (l >= ql and r <= qr) {lc(o) = c, rc(o) = c;dat(o) = 1;lazy(o) = c;return ;}pushdown(o);int mid = l + r >> 1;if (ql <= mid) change(l, mid, ls(o), ql, qr, c);if (qr > mid) change(mid + 1, r, rs(o), ql, qr, c);pushup(o);
}int query(int l, int r, int o, int ql, int qr)
{if (l >= ql and r <= qr) return dat(o);pushdown(o);int mid = l + r >> 1;int res = 0;if (ql <= mid) res += query(l, mid, ls(o), ql, qr);if (qr > mid) res += query(mid + 1, r, rs(o), ql, qr);if (ql <= mid and qr > mid and rc(ls(o)) == lc(rs(o))) res--;return res;
}int Find(int l, int r, int o, int p) 
{if (l == r) return lc(o);pushdown(o);int mid = l + r >> 1;if (p <= mid) return Find(l, mid, ls(o), p);else return Find(mid + 1, r, rs(o), p);
}inline void changes(int x, int y, int c)
{while(top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);change(1, n, 1, id[top[x]], id[x], c);x = fa[top[x]];}if (id[x] > id[y]) swap(x, y);change(1, n, 1, id[x], id[y], c);
}inline int querys(int x, int y)
{int res = 0;int lst1 = 0, lst2 = 0;while(top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);res += query(1, n, 1, id[top[x]], id[x]);lst1 = Find(1, n, 1, id[top[x]]), lst2 = Find(1, n, 1, id[fa[top[x]]]);if (lst1 == lst2) res--;x = fa[top[x]];}if (id[x] > id[y]) swap(x, y);res += query(1, n, 1, id[x], id[y]);return res;
}int main()
{n = read(), m = read();for (reg int i = 1 ; i <= n ; i ++) a[i] = read();for (reg int i = 1 ; i < n ; i ++){int x = read(), y = read();add(x, y), add(y, x);}cnt = 0;dep[1] = 1;dfs(1, 0), efs(1, 1);Build(1, n, 1);while(m--){char ch;cin >> ch;if (ch == 'C') {int x = read(), y = read(), z = read();changes(x, y, z);} else {int x = read(), y = read();printf("%d\n", querys(x, y));}}return 0;
}