Dylan's Blog
0%

BZOJ2243 染色 [树连剖分+线段树]

Posted on Edited on In

问题描述：

给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段） 请你写一个程序依次完成这m个操作。

输入：

第一行包含2个整数n和m，分别表示节点数和操作数； 第二行包含n个正整数表示n个节点的初始颜色 下面n-1行每行包含两个整数x和y，表示x和y之间有一条无向边。 下面m行每行描述一个操作： “C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c； “Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

输出：

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

思路：

数据结构题。。。思维含量不高，要注意很多细节

首先对于树上路径的操作和询问一般不难想到用树剖。然后就考虑如果维护一个序列的颜色段数量，以及修改操作。这种序列问题一般用线段树维护，线段树节点储存：左端及右端颜色，区间颜色段总数，lazytag。up函数也稍微修改一下。这样就解决了在序列上的问题。

接着考虑树剖，对于树上区间的合并要注意特殊处理链的左右端点问题，要分别记录两条链的端点颜色，在合并时要分清是那一条链。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<bits/stdc++.h>
#define ls (root<<1)
#define rs (root<<1|1)
#define mid (l+r>>1)
#define MAXN 100005
using namespace std;

int n, m, ans, cnt, head[MAXN], w[MAXN];
int sum[MAXN*4], lcol[MAXN*4], rcol[MAXN*4], tag[MAXN*4];
int ind, Lcol, Rcol, val[MAXN], id[MAXN], f[MAXN], size[MAXN], dep[MAXN], son[MAXN], top[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void up(int root)
{
    sum[root]=sum[ls]+sum[rs];
    if(rcol[ls]==lcol[rs]) sum[root]--;
    lcol[root]=lcol[ls];
    rcol[root]=rcol[rs];
}

void down(int root, int l, int r)
{
    if(!tag[root]) return;
    sum[rs]=sum[ls]=1;
    lcol[ls]=rcol[ls]=tag[root];
    lcol[rs]=rcol[rs]=tag[root];
    tag[ls]=tag[rs]=tag[root];
    tag[root]=0;
}

void build(int root, int l, int r)
{
    if(l==r)
    {
        sum[root]=1;
        lcol[root]=rcol[root]=val[l];
        return;
    }
    build(ls, l, mid);
    build(rs, mid+1, r);
    up(root);
}

void update(int root, int l, int r, int x, int y, int k)
{
    if(l>y || r<x) return;
    if(l>=x && r<=y)
    {
        sum[root]=1;
        tag[root]=rcol[root]=lcol[root]=k;
        return;
    }
    down(root, l, r);
    update(ls, l, mid, x, y, k);
    update(rs, mid+1, r, x, y, k);
    up(root);
}

void query(int root, int l, int r, int x, int y)
{
    if (l>y || r<x) return;
    if(l==x) Lcol=lcol[root];
    if(r==y) Rcol=rcol[root];
    if(x<=l && y>=r)
    {
        ans+=sum[root];
        return;
    }
    down(root, l, r);
    query(ls, l, mid, x, y);
    query(rs, mid+1, r, x, y);
    if(mid>=x && mid+1<=y && rcol[ls]==lcol[rs]) ans--;
}

void dfs1(int x, int fa)
{
    int maxson=-1; f[x]=fa; size[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dep[to]=dep[x]+1;
        dfs1(to, x);
        size[x]+=size[to];
        if(size[to]>maxson) son[x]=to, maxson=size[to];
    }
}

void dfs2(int x, int topf)
{
    id[x]=++ind; val[ind]=w[x]; top[x]=topf;
    if(!son[x]) return;
    dfs2(son[x], topf);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=f[x] && to!=son[x]) dfs2(to, to);
    }
}

void update1(int x, int y, int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x, y);
        update(1, 1, n, id[top[x]], id[x], k);
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x, y);
    update(1, 1, n, id[x], id[y], k);
}

int query1(int x, int y)
{
    int last1=0, last2=0; ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x, y), swap(last1, last2);
        query(1, 1, n, id[top[x]], id[x]);
        if(Rcol==last1) ans--;
        last1=Lcol;
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x, y), swap(last1, last2);
    query(1, 1, n, id[x], id[y]);
    if(Lcol==last1) ans--;
    if(Rcol==last2) ans--;
    return ans;
}

int main()
{
    int x, y, a, b, c; char opt;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &w[i]);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    for(int i=1; i<=m; i++)
    {
        scanf("%s%d%d", &opt, &a, &b);
        if(opt=='C') {scanf("%d", &c); update1(a, b, c);}
        if(opt=='Q') printf("%d\n", query1(a, b));
    }
}