题目地址

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 250005
#define endl '\n'
int n, m, a[maxn], b[maxn], bl[maxn], cnt, h[maxn], ol[maxn], cs, vis[maxn], fs[maxn], la[maxn], dep[maxn], fa[maxn][20], num, ans[maxn],  cntt[maxn], st[maxn];
struct node {
	int next, to;
} e[maxn];
struct dian {
	int id, l, r, lc;
} q[maxn];
bool cmp(dian a, dian b) {
	if (a.l / num != b.l / num)return a.l < b.l;
	else return a.r < b.r;
}
void add(int u, int v) {
	e[++cnt].to = v;
	e[cnt].next = h[u];
	h[u] = cnt;
}
void dfs(int u) {
	ol[++cs] = u;
	fs[u] = cs;
	vis[u]=1;
	for (int i = h[u]; i; i = e[i].next) {
		int v = e[i].to;
		if (!vis[v])dfs(v);
	}
	ol[++cs] = u;
	la[u] = cs;
}
void dfs2(int u,int p){
	fa[u][0]=p;
	dep[u]=dep[p]+1;
	for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].to;
		if(v!=p)dfs2(v,u);
	}
}
int lca(int a, int b) {
	if (dep[a] < dep[b])swap(a, b);
	for (int i = 15; i >= 0; i--) {
		if (dep[fa[a][i]] >= dep[b]) {
			a = fa[a][i];
		}
	}
	if (a == b)return a;
	for (int i = 15; i >= 0; i--) {
		if (fa[a][i] != fa[b][i]) {
			a = fa[a][i];
			b = fa[b][i];
		}
	}
	return fa[a][0];
}
void ad(int x, int &res) {
	st[x] ^= 1;
	if (st[x]) {
		if (!cntt[a[x]]) res++;
		cntt[a[x]]++;
	} else {
		cntt[a[x]]--;
		if (!cntt[a[x]]) res--;
	}
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + n + 1);
	int un = unique(b + 1, b + 1 + n) - b - 1;
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(b + 1, b + 1 + un, a[i]) - b;
	}
	for (int i = 1; i <= n - 1; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
	}
	dfs(1);
	dfs2(1,1);
//	for(int i=1;i<=cs;i++)cout<<ol[i]<<" ";
//	cout<<endl;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		if (fs[a] > fs[b])swap(a, b);
		int p = lca(a, b);
		//cout<<p<<endl;
		if (p == a)q[i] = {i, fs[a], fs[b], 0};
		else q[i] = {i, la[a], fs[b], p};
	}
	num = sqrt(cs);
	sort(q+1, q + m + 1, cmp);
	for (int k = 1, res = 0, i = 0, j = 1; k <= m; k++) {
		int id = q[k].id, l = q[k].l, r = q[k].r, p = q[k].lc;
		while (i < r) ad(ol[++i], res);
		while (i > r) ad(ol[i--], res);
		while (j < l) ad(ol[j++], res);
		while (j > l) ad(ol[--j], res);
		if (p!=0) ad(p, res);
		ans[id] = res;
		if (p!=0) ad(p, res);
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

顺便问一下spoj怎么下数据啊。 按照vjudge上是跑到了最后一个点才WA。但是根本看不到哪里错了或者数据在哪。