题目链接

提交记录

调试输出有点小多，忽略就好了

#include <iostream>
#include <set>
#include <algorithm>
#include <cassert>
#include <vector>
using namespace std;

#define cerr if(0)cout

int n, m, q, root = 1;

inline void train() {
	   ios::sync_with_stdio(false);
	   cin.tie(0);
	   cout.tie(0);
}

inline int maxi(int a, int b) {
	return a > b ? a : b;
}

inline int mini(int a, int b) {
	return a < b ? a : b;
}

/*
Solution:
1. 树剖，但是子节点连续编号，再编号重儿子
2. 离线所有询问，扫描线处理
3. ODT 区间推平（只会推 m 次，复杂度正确） 
*/


constexpr int N = 1e5+4, NS = 4e5+4;

#define assume(condition) assert((condition))

inline void xassume(bool condition) {
	if (!condition) {
		cout << "ABABABA" << endl;
		exit(0);// Trigger WA
	}
}

// Chtholly tree, from: https://www.luogu.com.cn/record/175221207 &
// https://www.luogu.com.cn/record/180098957
// Chtholly, go straight ahead!

struct chtholly {
	int b, e;	// [b, e).
	mutable int val;
	chtholly() {
		
	}
	chtholly(int b, int e, int val = 0) : b(b), e(e), val(val) {

	}
	int length() const {
		return e-b+1;
	}
};

bool operator < (const chtholly &a, const chtholly &b) {
	if (a.b == b.b) return a.e < b.e;	// Used for lower_bound.
	return a.b < b.b;
}
// WARNING: In the following data-maintainer, the chtholly tree's data should be immutable.

set<chtholly> ctree;

int tarray[NS];

inline int lowbit(int x) {
	return x & (-x);
}

inline int query(int x) {
	if (x <= 0) return 0;
	int sum = 0;
	while (x) {
		sum += tarray[x];
		x ^= lowbit(x);
	}
	return sum;
}

inline void update(int x, int val) {
	if (x <= 0) return;	// Ignored
	while (x < NS) {
		tarray[x] += val;
		x += lowbit(x);
	}
}

void erase_base(set<chtholly>::iterator& sit) {
#ifndef ONLINE_JUDGE
	auto &target = *sit;
	//cerr << "Iterator-Erasing [" << target.b << "," << target.e << ") = " << target.length() << " sized " << target.val << endl;
#endif
	update(sit->val, -(sit->length()));
	sit = ctree.erase(sit);
}

void insert_base(const chtholly &source) {
	if (ctree.count(source)) return;
	//cerr << "Adding [" << source.b << "," << source.e << ") = " << source.length() << " sized " << source.val << endl;
	ctree.insert(source);
	update(source.val, source.length());
}

// [l, r] definition now works

// Split only, no real change
set<chtholly>::iterator split_ch(int x) {
	if (x >= n) return ctree.end();
	auto it = --ctree.upper_bound(chtholly(x, x, 0));
	xassume(it != ctree.end());
	if (it->b == x) return it;
	int l = it->b, r = it->e, v = it->val;
	ctree.erase(it);
	ctree.insert(chtholly(l, x-1, v));
	return ctree.insert(chtholly(x, r, v)).first;
}

void update_ch(int l, int r, int v) {
	auto itr = split_ch(r+1), itl = split_ch(l);
	for (; itl != itr; erase_base(itl)) xassume(itl != ctree.end());
	auto cd = chtholly(l, r, v);
	insert_base(cd);
	//ctree.insert(cd);
}
//set<chtholly, data_comparer> data_cht;	// Need to sync

vector<int> tr[N];
// 0 for invalidated.
//int ref[N];
int dfn[N], dcnt = 1, sz[N], depth[N], dspread[N], hson[N], dstart[N], drange[N], father[N], htop[N];	// dcnt: Current valid.
bool is_hson[N], is_head[N];

void dfs1(int cur, int fa) {
	father[cur] = fa;
	depth[cur] = depth[fa] + 1;
	sz[cur] = 1;
	int smax = 0, smat = 0;
	for (auto &i : tr[cur]) {
		if (i == fa) continue;
		dfs1(i, cur);
		sz[cur] += sz[i];
		if (sz[i] > smax) {
			smax = sz[i];
			smat = i;
		}
	}
	is_hson[smat] = true;
	hson[cur] = smat;
}

// Only symbol descendants.
void dfs2(int cur, int fa) {
	if (is_hson[cur] && is_hson[fa]) {
		if (fa != 1 && is_hson[father[fa]]) dspread[cur] = dspread[fa];
		htop[cur] = htop[fa];
	}
	else htop[cur] = cur;
	if (is_hson[cur] && (!is_hson[fa])) {
		is_head[cur] = true;
	}
	drange[cur] = dfn[cur];
	dstart[cur] = (tr[cur].size() > 1) ? (n+1) : dfn[cur];
	for (auto &i : tr[cur]) {
		if (i == fa) continue;
		dfn[i] = dcnt;
//		ref[dcnt] = i;
		dcnt++;
		dstart[cur] = mini(dstart[cur], dfn[i]);
		drange[cur] = maxi(drange[cur], dfn[i]);
	}
	dspread[cur] = maxi(dspread[cur], drange[cur]);
	if (hson[cur]) dfs2(hson[cur], cur);
	for (auto &i : tr[cur]) {
		if (i == fa || i == hson[cur]) continue;
		dfs2(i, cur);
	}
}

struct queries {
	int l, r, id;
};

queries qs[N];
int xs[N], ys[N], ans[N];

bool cmp(const queries &a, const queries &b) {
	if (a.r == b.r) return a.l < b.l;
	return a.r < b.r;
}

int main() {

	//freopen("test.in", "r", stdin);
	//freopen("test.out", "w", stdout);

	train();
	
	// Initialize chtholly

	cin>>n>>m>>q;
	ctree.insert(chtholly(0, n-1, 0));
	for (int i = 0; i < n-1; i++) {
		int a,b;
		cin>>a>>b;
		tr[a].push_back(b);
		tr[b].push_back(a);
	}
	dfs1(1, 1);
//	ref[0] = 1;
	htop[1] = 1;
	is_hson[1] = true;
	dfs2(1, 1);
#ifndef ONLINE_JUDGE
	//for (int i = 1; i <= n; i++) cerr<<dfn[i]<<' ';
	//cerr<<endl;
	//for (int i = 1; i <= n; i++) cerr << drange[i] << ' ';
	//cerr << endl;
	//for (int i = 1; i <= n; i++) cerr<<hson[i]<<' ';
	//cerr<<endl;
	//for (int i = 1; i <= n; i++) cerr<<htop[i]<<' ';
	//cerr<<endl;
	//for (int i = 1; i <= n; i++) cerr << dspread[i] << ' ';
	//cerr << endl;
#endif
	for (int i = 1; i <= m; i++) cin>>xs[i]>>ys[i];
	for (int i = 1; i <= q; i++) {
		cin>>qs[i].l>>qs[i].r;
		qs[i].id = i;
	}
	sort(qs+1,qs+q+1,cmp);
	int lastr = 1;
	for (int i = 1; i <= q; i++) {
		for (; lastr <= qs[i].r; lastr++) {
			// Scan through r-th chain:
			//cerr << "============== Scanning " << lastr << endl;
			int p1 = xs[lastr], p2 = ys[lastr];
			while (htop[p1] != htop[p2]) {
				if (depth[htop[p1]] < depth[htop[p2]]) swap(p1, p2);	// Then deal with p1
				// Deal with the whole chain through dfn[...] calls
				//update_th(htop[p1], p1, lastr);
				//p1 = father[htop[p1]];
				int tmp = p1;
				int ctop = p1 = htop[p1];
				bool ok = hson[p1] && depth[hson[p1]] <= depth[tmp];
				if (ok) {
					p1 = hson[p1];
					//cerr << "CH update " << p1 << " -- " << tmp << " as " << dfn[p1] << " -> " << dspread[tmp] << endl;
					//update_th(p1, tmp, lastr);
					update_ch(dfn[p1], dspread[tmp], lastr);
					p1 = tmp;	// Revoke
				}
				// Already top (will still be dealt with):
				//cerr << "CH update " << p1 << " as " << dfn[p1] << " and " << dstart[p1] << "~" << drange[p1] << endl;
				update_ch(dfn[p1], dfn[p1], lastr);
				update_ch(dstart[p1], drange[p1], lastr);
				
				if (p1 != father[p1]) {
					p1 = father[p1];
				}
			}
			//cerr << "End of jumper.\n";
			if (depth[p1] > depth[p2]) swap(p1, p2);
			int eson = p1;// hson[p1];
			bool ok2 = true;
			//if ((p1 == p2) || is_head[p1]) {
				if (hson[p1] && depth[hson[p1]] <= depth[p2]) eson = hson[p1];
				else ok2 = false;
			//}
			if (depth[eson] > depth[p2]) eson = p2;
			//cerr << "Target: " << p1 << "; " << p2 << " desc. " << eson << endl;
			//if (is_hson[p1] && (!is_hson[father[p1]])) {
				//cerr << "CH update " << eson << " -- " << p2 << " as " << dfn[eson] << " -> " << dspread[p2] << endl;
				//cerr << "Also: " << dstart[eson] << "~" << drange[eson] << ";" << dstart[p2] << "~" << drange[p2] << endl;
				if (ok2) {
					update_ch(dfn[eson], dspread[p2], lastr);
				}
				else {
					update_ch(dfn[eson], dfn[eson], lastr);
					update_ch(dfn[p2], dfn[p2], lastr);
					update_ch(dstart[eson], drange[eson], lastr);
					update_ch(dstart[p2], drange[p2], lastr);
				}
				//update_th(eson, p2, lastr);
				//cerr << "CH update " << p1 << " as " << dfn[p1] << " and " << dstart[p1] << "~" << drange[p1] << endl;
				update_ch(dfn[p1], dfn[p1], lastr);
				update_ch(dstart[p1], drange[p1], lastr);
			//}
			//else {
			//	cerr << "TH update " << p1 << " -- " << p2 << endl;
			//	update_th(p1, p2, lastr);
			//}
			if (p1 != father[p1]) {
				update_ch(dfn[father[p1]], dfn[father[p1]], lastr);
			}
		}
		ans[qs[i].id] = (query(qs[i].r) - query(qs[i].l - 1));
	}
	for (int i = 1; i <= q; i++) cout<<ans[i]<<'\n';
	
	cout<<flush;

	return 0;
}