今天晚上的效率比白天高啊。
树上莫队的另一道题。比糖果公园好写到哪里去了。
然后手写链表丑掉了导致调试半天+RE了一发。我还是太年轻了。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct node {
int t;
node *next;
} edge;
const int maxn = 50009;
const int maxm = 100009;
const int maxl = 17;
node nlst[maxn], *np(nlst);
struct chain {
int sz;
node *hd, *tl;
chain() {
hd = tl = 0;
sz = 0;
}
inline void clear() {
hd = tl = 0;
sz = 0;
}
inline void push(int x) {
np-> t = x;
np-> next = 0;
if (sz) {
tl-> next = np;
tl = np;
}
else {
hd = np;
tl = np;
}
++ np;
++ sz;
}
inline void merge(chain a) {
if (a. sz) {
if (sz) {
tl-> next = a. hd;
tl = a. tl;
}
else {
hd = a. hd;
tl = a. tl;
}
sz += a. sz;
}
}
};
struct query {
int a, b, x, y, i;
};
int n, m, bsz, ans[maxm], cnt[maxn], fb[maxn], col[maxn], tb;
int d[maxn], ath[maxn][maxl];
edge elst[maxn << 1], *ep(elst), *head[maxn];
query q[maxm];
inline bool operator <(const query& a, const query& b) {
return (fb[a. a] < fb[b. a]) || (fb[a. a] == fb[b. a] && fb[a. b] < fb[b. b]);
}
inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}
chain dfs(int p) {
for (int i = 1; i < maxl; ++ i)
ath[p][i] = ath[ath[p][i - 1]][i - 1];
chain w;
for (edge* e = head[p]; e; e = e-> next)
if (e-> t != ath[p][0]) {
ath[e-> t][0] = p;
d[e-> t] = d[p] + 1;
chain g(dfs(e-> t));
w. merge(g);
if (w. sz >= bsz) {
++ tb;
for (node* it = w. hd; it; it = it-> next)
fb[it-> t] = tb;
w. clear();
}
}
w. push(p);
return w;
}
void divide() {
d[0] = 1;
tb = 0;
chain g(dfs(0));
for (node* it = g. hd; it; it = it-> next)
fb[it-> t] = tb;
}
int LCA(int u, int v) {
if (d[u] < d[v])
swap(u, v);
for (int i = maxl - 1; i >= 0; -- i)
if (d[ath[u][i]] >= d[v])
u = ath[u][i];
if (u == v)
return u;
for (int i = maxl - 1; i >= 0; -- i)
if (ath[u][i] ^ ath[v][i]) {
u = ath[u][i];
v = ath[v][i];
}
return ath[u][0];
}
inline void rmVertex(int p, int& ans) {
if (p && ! -- cnt[col[p]])
-- ans;
}
inline void insVertex(int p, int& ans) {
if (p && !(cnt[col[p]] ++))
++ ans;
}
void moveVertex(int& u, int v, int g, int& ans) {
int a(LCA(u, v)), t(LCA(a, g));
if (a == t) {
int x(LCA(u, g)), y(LCA(v, g));
if (d[x] > d[y])
t = x;
else
t = y;
if (LCA(t, u) == t) {
for (int p = g; p ^ t; p = ath[p][0])
insVertex(p, ans);
for (int p = u; p ^ t; p = ath[p][0])
rmVertex(p, ans);
}
else {
for (int p = g; p ^ t; p = ath[p][0])
insVertex(p, ans);
for (int p = u; p ^ a; p = ath[p][0])
rmVertex(p, ans);
for (int p = ath[t][0]; p ^ a; p = ath[p][0])
rmVertex(p, ans);
rmVertex(a, ans);
}
}
else {
for (int p = u; p ^ a; p = ath[p][0])
rmVertex(p, ans);
for (int p = g; p ^ t; p = ath[p][0])
insVertex(p, ans);
insVertex(t, ans);
for (int p = ath[a][0]; p ^ t; p = ath[p][0])
insVertex(p, ans);
}
u = g;
}
void cptMo() {
int u(1), v(1), cans(1);
memset(cnt, 0, sizeof(cnt));
cnt[col[1]] = 1;
sort(q, q + m);
for (int i = 0; i < m; ++ i) {
moveVertex(u, v, q[i]. a, cans);
moveVertex(v, u, q[i]. b, cans);
ans[q[i]. i] = cans;
if ((q[i]. x || q[i]. y) && q[i]. x != q[i]. y)
ans[q[i]. i] -= (cnt[q[i]. x] && cnt[q[i]. y]);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d", &n, &m);
bsz = (int)pow(n, 0.5) + 1;
for (int i = 1; i <= n; ++ i)
scanf("%d", col + i);
memset(head, 0, sizeof(head));
for (int i = 0; i < n; ++ i) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
for (int i = 0; i < m; ++ i) {
scanf("%d%d%d%d", &q[i]. a, &q[i]. b, &q[i]. x, &q[i]. y);
q[i]. i = i;
}
divide();
for (int i = 0; i < m; ++ i)
if (fb[q[i]. a] > fb[q[i]. b])
swap(q[i]. a, q[i]. b);
cptMo();
for (int i = 0; i < m; ++ i)
printf("%d\n", ans[i]);
}
