记录编号	585495	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO19 DEC Gold]Milk Visits	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	2.375 s
提交时间	2023-12-14 20:07:31	内存使用	9.48 MiB

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using tup = std::tuple<int, int, int, int>;
using pii = std::pair<int, int>;

constexpr int maxn = 1e5 + 5;
int n, m, a[maxn], dfn[maxn], rev[maxn], dfc, top[maxn], siz[maxn], dep[maxn], fa[maxn], son[maxn], buc[maxn], ans[maxn];
std::vector<int> G[maxn];
std::vector<std::tuple<int, int, int, int>> qry;

void dfs1(int u, int ff) {
	siz[u] = 1; dep[u] = dep[fa[u] = ff] + 1;
	for (auto& v : G[u]) {
		if (v == ff) continue ;
		dfs1(v, u); siz[u] += siz[v];
		if (siz[v] > siz[son[u]]) son[u] = v;
	} 
	return ;
}

void dfs2(int u, int tp) {
	top[rev[dfn[u] = ++dfc] = u] = tp;
	if (!son[u]) return ;
	dfs2(son[u], tp);
	for (auto& v : G[u])
		if (v != fa[u] && v != son[u]) dfs2(v, v);
	return ;
}

void forw(int u, int v, int w, int id) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
		qry.pb(w, id, dfn[top[u]] - 1, -1);
		qry.pb(w, id, dfn[u], 1);
		u = fa[top[u]];
	}
	if (dep[u] > dep[v]) std::swap(u, v);
	qry.pb(w, id, dfn[u] - 1, -1);
	qry.pb(w, id, dfn[v], 1);
	return ;
}

int main() {
	freopen("_milkvisits.in", "r", stdin);
	freopen("_milkvisits.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for (int i = 1; i < n; ++i) {
		int u, v; scanf("%d %d", &u, &v);
		G[u].pb(v); G[v].pb(u);
	}
	dfs1(1, 0); dfs2(1, 0);
	for (int i = 1; i <= m; ++i) {
		int u, v, t; scanf("%d %d %d", &u, &v, &t);
		forw(u, v, t, i);
	}
	int j = 1;
	std::sort(qry.begin(), qry.end(), [&](const tup& lhs, const tup& rhs) {
		return std::get<2>(lhs) < std::get<2>(rhs);
	});
	for (auto& p : qry) {
		int w, id, x, v; std::tie(w, id, x, v) = p;
		for (; j <= x; ++j) ++buc[a[rev[j]]];
		ans[id] += v * buc[w];
	}
	for (int i = 1; i <= m; ++i)
		printf("%d", ans[i] > 0);
	return 0;
}