P2486 [SDOI2011]染色
blank_space · · 个人记录
P2486 [SDOI2011]染色
很好的树剖题
与一般的树剖题不一样的是线段树除维护区间内颜色的数量以外还要维护每一个区间的左侧和右侧的颜色
因为在合并的时候如果左侧区间的右侧的颜色与右侧区间的左侧的颜色相同 那么向上传递时颜色数量要减一
这是在同一区间内的情况 在不同区间内 也就是在不同树链上的情况还要考虑树链的交界处
因为每次处理的时候先处理的都是链顶深度比较大的树链 所以要处理的下一条树链在线段树中所对应的区间一定在这条树链的前面
所以我们要判断的就是当前树链的所对应区间的左端与下一条树链所对应区间的右端的颜色是否相同 相同的话减一就好了 要注意的是左右两边分开存储
然后是跳到同一条链上之后 因为同一条链上在线段树中对应的由左到右区间是由上向下的 所以上方的点的颜色对应的就是区间左侧 下方的点的颜色对应的是区间右侧 分别与前面向同一条链上跳的时候存储的左右两边的左侧颜色比较就可以了
具体可以看代码理解一下
code：
/*
Time: 11.25
Worker: Blank_space
Source: P2486 [SDOI2011]染色
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#define Orz cout<<"ZXS AK IOI"<<'\n';
#define ll long long
#define emm(x) memset(x,0,sizeof x)
#define emmm(x) memset(x,0x3f,sizeof x)
using namespace std;
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int FFF = 0x8fffffff;
/*------------------------------------常量定义*/
int CL, CR, n, m, a[C], dep[C], fa[C], siz[C], dfn[C], pos[C], son[C], top[C], cnt;
struct edge{
int v, nxt;
}e[C << 1];
int head[C], js;
/*------------------------------------变量定义*/
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
/*----------------------------------------快读*/
void add_edge(int u, int v)
{
e[++js].v = v;
e[js].nxt = head[u];
head[u] = js;
}
namespace tree {
#define ls(x) x << 1
#define rs(x) x << 1 | 1
struct node {
int l, r, mid, len, cl, cr, sum, lzy;
}t[C << 2];
void f(int p, int k)
{
t[p].cl = t[p].cr = t[p].lzy = k; t[p].sum = 1;
}
void push_up(int p)
{
t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
t[p].cl = t[ls(p)].cl; t[p].cr = t[rs(p)].cr;
if(t[ls(p)].cr == t[rs(p)].cl) t[p].sum --;
}
void push_down(int p)
{
f(ls(p), t[p].lzy); f(rs(p), t[p].lzy); t[p].lzy = 0;
}
void build(int p, int l, int r)
{
t[p].l = l; t[p].r = r; t[p].len = r - l + 1; t[p].mid = (l + r) >> 1;
if(l == r) {t[p].sum = 1; t[p].cl = t[p].cr = a[pos[l]]; return ;}
build(ls(p), l, t[p].mid); build(rs(p), t[p].mid + 1, r); push_up(p);
}
void up_date(int p, int l, int r, int k)
{
if(t[p].l == l && t[p].r == r) {f(p, k); return ;}
if(t[p].lzy) push_down(p);
if(r <= t[p].mid) up_date(ls(p), l, r, k);
else if(l > t[p].mid) up_date(rs(p), l, r, k);
else {up_date(ls(p), l, t[p].mid, k); up_date(rs(p), t[p].mid + 1, r, k);}
push_up(p);
}
int query(int p, int l, int r, int L, int R)
{
if(t[p].l == L) CL = t[p].cl; if(t[p].r == R) CR = t[p].cr;
if(t[p].l == l && t[p].r == r) return t[p].sum;
if(t[p].lzy) push_down(p);
if(r <= t[p].mid) return query(ls(p), l, r, L, R);
else if(l > t[p].mid) return query(rs(p), l, r, L, R);
else {
int res = query(ls(p), l, t[p].mid, L, R) + query(rs(p), t[p].mid + 1, r, L, R);
if(t[ls(p)].cr == t[rs(p)].cl) res--; return res;
}
}
}
namespace cut {
void dfs(int u, int pre)
{
fa[u] = pre; dep[u] = dep[pre] + 1; siz[u] = 1;
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if(v == pre) continue;
dfs(v, u); siz[u] += siz[v];
if(!son[u] || siz[son[u]] < siz[v]) son[u] = v;
}
}
void dfs2(int u, int tp)
{
dfn[u] = ++cnt; pos[cnt] = u; top[u] = tp;
if(!son[u]) return ; dfs2(son[u], tp);
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
void up_date(int x, int y, int k)
{
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
tree::up_date(1, dfn[top[x]], dfn[x], k);
x = fa[top[x]];
}
if(dfn[x] > dfn[y]) swap(x, y);
tree::up_date(1, dfn[x], dfn[y], k);
}
int query(int x, int y)
{
int res = 0, cx = -1, cy = -1;
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y), swap(cx, cy);
res += tree::query(1, dfn[top[x]], dfn[x], dfn[top[x]], dfn[x]);
if(CR == cx) res--; cx = CL; x = fa[top[x]];
}
if(dfn[x] > dfn[y]) swap(x, y), swap(cx, cy);
res += tree::query(1, dfn[x], dfn[y], dfn[x], dfn[y]);
if(CL == cx) res --; if(CR == cy) res --;
return res;
}
}
/*----------------------------------------函数*/
int main()
{
// freopen("","r",stdin);
// freopen("","w",stdout);
n = read(); m = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i < n; i++)
{
int x = read(), y = read();
add_edge(x, y); add_edge(y, x);
}
cut::dfs(1, 0); cut::dfs2(1, 1); tree::build(1, 1, cnt);
for(int i = 1; i <= m; i++)
{
char op; cin >> op;
if(op == 'Q')
{
int x = read(), y = read();
printf("%d\n",cut::query(x, y));
}
if(op == 'C')
{
int x = read(), y = read(), z = read();
cut::up_date(x, y, z);
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}