题解

时间内存最优（击败花神）

#include<bits/stdc++.h>
#define ll long long
#define N 100010
using namespace std;
int n, m, x, y, w, g, gg, tot, s[N], v[N], hs[N], fa[N], ans[N], dep[N], anc[N], head[N];
struct rec
{
	int to, next;
}a[N<<1];
struct node
{
	int x, v;
	bool operator < (const node b) const
	{
		return x < b.x;
	}
}pt[N];
struct nodee
{
	int t, x, y, v;
	bool operator < (const nodee b) const
	{
		return t < b.t;
	}
}q[N];
struct Tree
{
	int a[N<<2];
	#define ls x*2
	#define rs x*2+1
	void up(int x)
	{
		a[x] = a[ls] + a[rs];
		return;
	}
	void add(int x, int L, int R, int w, int s)
	{
		if (L == w && w == R)
		{
			a[x] += s;
			return;
		}
		int mid = L + R >> 1;
		if (w <= mid) add(ls, L, mid, w, s);
		else add(rs, mid + 1, R, w, s);
		up(x);
	}
	int ask(int x, int L, int R, int l, int r)
	{
		if (L == l && R == r) return a[x];
		int mid = L + R >> 1;
		if (r <= mid) return ask(ls, L, mid, l, r);
		if (l > mid) return ask(rs, mid + 1, R, l, r);
		return ask(ls, L, mid, l, mid) + ask(rs, mid + 1, R, mid + 1, r);
	}
}T;
void add(int x, int y)
{
	a[++tot].to = y;
	a[tot].next = head[x];
	head[x] = tot;
	return; 
}
void dfs1(int x)
{
	s[x] = 1;
	for (int i = head[x]; i; i = a[i].next)
		if (a[i].to != fa[x])
		{
			fa[a[i].to] = x;
			dep[a[i].to] = dep[x] + 1;
			dfs1(a[i].to);
			s[x] += s[a[i].to];
			if (s[a[i].to] > s[hs[x]]) hs[x] = a[i].to;
		}
	return;
}
void dfs2(int x, int y)
{
	anc[x] = y;
	v[x] = ++w;
	if (hs[x]) dfs2(hs[x], y);
	for (int i = head[x]; i; i = a[i].next)
		if (a[i].to != fa[x] && a[i].to != hs[x])
			dfs2(a[i].to, a[i].to);
}
int ask(int x, int y)//求和
{
	int g = 0;
	while (anc[x] != anc[y])
	{
		if (dep[anc[x]] < dep[anc[y]]) swap(x, y);
		g += T.ask(1, 1, n, v[anc[x]], v[x]);
		x = fa[anc[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	g += T.ask(1, 1, n, v[x], v[y]);
	return g; 
}
int main()
{
	cin>>n>>m;
	for (int i = 1; i <= n; ++i)
	{
		cin>>pt[i].x;
		pt[i].v = i;
	}
	for (int i = 1; i < n; ++i)
	{
		cin>>x>>y;
		add(x, y);
		add(y, x);
	}
	for (int i = 1; i <= m; ++i)
	{
		cin>>q[i].x>>q[i].y>>q[i].t;
		q[i].v = i;
	}
	sort(pt + 1, pt + 1 + n);
	sort(q + 1, q + 1 + m);
	fa[1] = dep[1] = 1;
	dfs1(1);
	dfs2(1, 1);
	g = 1;
	gg = 1;
	while(g <= n)
	{
		int h = g;
		while(pt[h].x == pt[g].x && h <= n) T.add(1, 1, n, v[pt[h].v], 1), h++;
		while(q[gg].t < pt[g].x && gg <= m) gg++;
		while(q[gg].t == pt[g].x && gg <= m) ans[q[gg].v] = ask(q[gg].x, q[gg].y), gg++;
		for (int i = g; i < h; ++i)
			T.add(1, 1, n, v[pt[i].v], -1);
		g = h;
	}
	for (int i = 1; i <= m; ++i)
		if (ans[i]) putchar('1');
		else putchar('0');
	return 0;
}

花神息怒，我不是故意的！