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
160
161
162
163
164
165
166
167
168
| #include <cstdio>
#include <algorithm>
const int MAXN = 100001;
struct Triple
{
int x, y, z;
Triple(const int a, const int b, const int c): x(a), y(b), z(c) { }
};
struct Edge { int v; Edge *next; };
Edge g[MAXN*2], *header[MAXN];
void AddEdge(const int x, const int y)
{
static int LinkSize;
Edge* const node = g+(LinkSize++);
node->v = y;
node->next = header[x];
header[x] = node;
}
//------SegmentTree:
int n;
struct SegmentNode { int count, tag, clef, crig; };
SegmentNode s[MAXN*4];
int _st, _ed, _x;
inline void clear(const int p, const int lef, const int rig)
{
if (!s[p].tag) return;
s[p].clef = s[p].crig = s[p].tag;
if (lef != rig)
s[p*2].tag = s[p*2+1].tag = s[p].tag;
s[p].count = 1;
s[p].tag = 0;
}
void _modify(const int p, const int lef, const int rig)
{
if (_st <= lef && rig <= _ed)
{
s[p].tag = _x;
clear(p, lef, rig);
return;
}
clear(p, lef, rig);
const int mid = (lef+rig)/2;
if (_st <= mid) _modify(p*2, lef, mid);
if (mid+1 <= _ed) _modify(p*2+1, mid+1, rig);
clear(p*2, lef, mid);
clear(p*2+1, mid+1, rig);
s[p].count = s[p*2].count + s[p*2+1].count;
s[p].clef = s[p*2].clef, s[p].crig = s[p*2+1].crig;
if (s[p*2].crig == s[p*2+1].clef) --s[p].count;
}
Triple _query(const int p, const int lef, const int rig)
{
clear(p, lef, rig);
if (_st <= lef && rig <= _ed) return Triple(s[p].clef, s[p].crig, s[p].count);
const int mid = (lef+rig)/2;
if (_st <= mid && mid+1 <= _ed)
{
const Triple tmp1 = _query(p*2, lef, mid);
const Triple tmp2 = _query(p*2+1, mid+1, rig);
Triple res(tmp1.x, tmp2.y, tmp1.z+tmp2.z);
if (tmp1.y == tmp2.x) --res.z;
return res;
}
if (_st <= mid) return _query(p*2, lef, mid);
return _query(p*2+1, mid+1, rig);
}
inline void Modify(const int st, const int ed, const int x)
{
_st = st, _ed = ed, _x = x;
_modify(1, 1, n);
}
inline Triple Query(const int st, const int ed)
{
_st = st, _ed = ed;
return _query(1, 1, n);
}
//------Heavy-Light Decomposition:
typedef int Array[MAXN];
Array hson, size, top, depth, number, parent;
void HLDdfs1(const int u)
{
hson[u] = 0, size[u] = 1;
for (Edge *e = header[u]; e; e = e->next)
if (e->v != parent[u])
{
parent[e->v] = u;
depth[e->v] = depth[u]+1;
HLDdfs1(e->v);
size[u] += size[e->v];
if (size[e->v] > size[hson[u]])
hson[u] = e->v;
}
}
void HLDdfs2(const int u, const int tp)
{
static int timestamp;
number[u] = ++timestamp, top[u] = tp;
if (hson[u])
HLDdfs2(hson[u], tp);
for (Edge *e = header[u]; e; e = e->next)
if (e->v != parent[u] && e->v != hson[u])
HLDdfs2(e->v, e->v);
}
void HLDChange(int a, int b, const int x)
{
int ta = top[a], tb = top[b];
while (ta != tb)
{
if (depth[ta] < depth[tb])
std::swap(ta, tb), std::swap(a, b);
Modify(number[ta], number[a], x);
a = parent[ta], ta = top[a];
}
if (depth[a] > depth[b]) std::swap(a, b);
Modify(number[a], number[b], x);
}
int HLDQuery(int a, int b)
{
int ta = top[a], tb = top[b];
int la = -1, lb = -1, res = 0;
while (ta != tb)
{
if (depth[ta] < depth[tb])
std::swap(ta, tb), std::swap(a, b), std::swap(la, lb);
const Triple tmp = Query(number[ta], number[a]);
res += tmp.z;
if (tmp.y == la) --res;
la = tmp.x;
a = parent[ta], ta = top[a];
}
if (depth[a] > depth[b]) std::swap(a, b), std::swap(la, lb);
const Triple tmp = Query(number[a], number[b]);
res += tmp.z;
if (tmp.x == la) --res;
if (tmp.y == lb) --res;
return res;
}
int m, c[MAXN];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", c+i);
for (int i = 1, x, y; i < n; ++i)
{
scanf("%d%d", &x, &y);
AddEdge(x, y);
AddEdge(y, x);
}
HLDdfs1(1);
HLDdfs2(1, 1);
for (int i = 1; i <= n; ++i)
Modify(number[i], number[i], ++c[i]);
for (int i = 0, st, ed, x; i < m; ++i)
{
char c;
scanf("\n%c%d%d", &c, &st, &ed);
if (c == 'Q')
printf("%d\n", HLDQuery(st, ed));
else
{
scanf("%d", &x);
HLDChange(st, ed, ++x);
}
}
}
|
