8分求调

#include <bits/stdc++.h>
using namespace std;
//LCA
typedef long long ll;
typedef pair<int, int> pll;
const int N = 1e5 + 10, M = 3e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][18];
string cow;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs() {
	queue<int> q;
	q.push(1);
	depth[1] = 1;
	while (q.size()) {
		int t = q.front();
		q.pop();
		for (int i = h[t] ; ~i ; i = ne[i]) {
			int j = e[i];
			if (depth[j] == 0) {
				q.push(j);
				depth[j] = depth[t] + 1;
				fa[j][0] = t;
				for (int k = 1 ; k <= 16 ; ++k) {
					fa[j][k] = fa[fa[j][k - 1]][k - 1];
				}
			}
		}
	}
}
bool lca(int a, int b, char c) {
	if (depth[a] < depth[b]) swap(a, b);
	if(cow[a] == c || cow[b] == c) return 1;
	for (int k = 16 ; k >= 0 ; --k) {
		if (depth[fa[a][k]] >= depth[b]) {
			if (cow[fa[a][k]] == c) return 1;
			a = fa[a][k];
		}
	}
	if (a == b) {
		if (cow[a] == c) return 1;
		else return 0;
	}
	for (int k = 16 ; k >= 0 ; --k) {
		if (fa[a][k] != fa[b][k]) {
			if (cow[fa[a][k]] == c || cow[fa[b][k]] == c) return 1;
			a = fa[a][k], b = fa[b][k];
		}
	}
	if (cow[fa[a][0]] == c || cow[fa[b][0]] == c) return 1;
	return 0;
}
int main() {
	cin >> n >> m >> cow;
	cow = '?' + cow;
	memset(h, -1, sizeof h);
	for (int i = 1 ; i < n ; ++i) {
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a);
	}
	bfs();
	string ans;
	while (m--) {
		int a, b;
		char op;
		cin >> a >> b >> op;
		if (lca(a, b, op)) ans += '1';
		else ans += '0';
	}
	cout << ans << endl;
	return 0;
}