题解：P12180 DerrickLo's City (UBC002C)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
const int MAXN = 1e5 + 5;

int p[MAXN];

struct NODE {
	vector<int> mi, ma;
	int n;

	NODE(int size, int *arr) {
		n = 1;
		while (n < size)
			n <<= 1;
		mi.resize(2 * n, INT_MAX);
		ma.resize(2 * n, INT_MIN);
		for (int i = 0; i < size; i++) {
			mi[i + n] = arr[i + 1];
			ma[i + n] = arr[i + 1];
		}
		for (int i = n - 1; i > 0; i--) {
			mi[i] = min(mi[2 * i], mi[2 * i + 1]);
			ma[i] = max(ma[2 * i], ma[2 * i + 1]);
		}
	}

	PII query(int l, int r) {
		l--;
		r--;
		int rmi = INT_MAX;
		int rma = INT_MIN;
		for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
			if (l % 2 == 1) {
				rmi = min(rmi, mi[l]);
				rma = max(rma, ma[l]);
				l++;
			}
			if (r % 2 == 0) {
				rmi = min(rmi, mi[r]);
				rma = max(rma, ma[r]);
				r--;
			}
		}
		return {rmi, rma};
	}
};
int n, q;
//int pma[200010];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		p[i] = 0;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		if (a < b) {
			if (p[b] == 0 || p[b] > a)
				p[b] = a;
		} else {
			if (p[a] == 0 || p[a] > b)
				p[a] = b;
		}
	}
	NODE st_min(n, p);
	vector<int> pma(MAXN);
	for (int i = 1; i <= n; i++)
		pma[i] = p[i];
	NODE st_max(n, pma.data());
	while (q--) {
		int l, r;
		cin >> l >> r;
		auto [mip, map] = st_min.query(l, r);
		if (map < l || mip > r) {
			cout << "Yes\n";
			continue;
		}
		int cntp = 0;
		int flag = -1;
		for (int i = l; i <= r; i++) {
			if (p[i] >= l && p[i] <= r) {
				cntp++;
				flag = p[i];
			}
		}
		if (cntp == 0) {
			cout << "Yes\n";
			continue;
		}
		bool valid = true;
		int p1 = flag;
		for (int i = l; i <= r; i++) {
			if (i == p1)
				continue;
			if (p[i] != p1 && (p[i] < l || p[i] > r))
				continue;
			valid = false;
			break;
		}
		if (valid && (p[p1] < l || p[p1] > r)) {
			cout << "Yes\n";
		} else {
			cout << "No\n";
		}
	}

	return 0;
}