BZOJ3757 苹果树

今天晚上的效率比白天高啊。

树上莫队的另一道题。比糖果公园好写到哪里去了。

然后手写链表丑掉了导致调试半天+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]);
}