bzoj4009 [HNOI2015]接水果 整体二分+扫描线+树状数组+dfs序

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=4009

题解

考虑怎样的情况就会有一个链覆盖另一个链。

设被覆盖的链为 \(a - b\)，覆盖的链为 \(x - y\)。假设有 \(dfn[a] < dfn[b], dfn[x] < dfn[y]\)

那么如果 \(a\) 是 \(b\) 的祖先，那么令 \(g\) 为 \(a\) 的子树中包含 \(b\) 的点，那么 \(x, y\) 中有一个点在 \(g\) 的子树外面，一个在 \(b\) 子树里面，即 \(x \in [1, dfn[g] - 1], y \in [dfn[b], dfn[b] + siz[b] - 1]\)，\(x \in [dfn[b], dfn[b] + siz[b] - 1], y \in [dfn[g] + siz[g], n]\)。

否则，那么 \(x, y\) 必然一个在 \(a\) 子树中，一个在 \(b\) 子树中。即 \(x \in [dfn[a], dfn[a] + siz[a] - 1]\)，\(y \in [dfn[b], dfn[b] + siz[b] - 1]\)。

那么我们不妨把上面的问题看成求出包含一个点的矩阵的权值的第 \(k\) 小。

这个问题似乎可以用扫描线+动态主席树来做。（就是带修改区间 \(k\) 小值啊）

但是应该整体二分更好写一写，整体二分以后转化为求出一个点被几个矩形覆盖，也是扫描线+树状数组维护。

但是我似乎已经忘了整体二分怎么写了，然后学了很久，写的时候写出了一堆的 bug，调了一整天才调完。

不过这个题目把询问转化为矩形维护的相关操作是一个很好的思想。

时间复杂度 \(O(q\log^2n)\)。

#include

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair pii;

template inline void read(I &x) {
	int f = 0, c;
	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
	x = c & 15;
	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
	f ? x = -x : 0;
}

const int N = 40000 + 7;

#define lowbit(x) ((x) & -(x))

int n, m, Q, dfc, cnt;
int dep[N], f[N], siz[N], son[N], top[N], dfn[N], pre[N], ans[N];
std::priority_queue > q;
struct Matrix {
	int x1, x2, y1, y2, v;
	inline bool operator < (const Matrix &b) const { return x1 < b.x1; }
} a[N << 1], a1[N << 1], a2[N << 1];
struct Point {
	int x, y, k, *ans;
	inline bool operator < (const Point &b) const { return x < b.x; }
} b[N], b1[N], b2[N];

struct Edge { int to, ne; } g[N << 1]; int head[N], tot;
inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }
inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }

inline void dfs1(int x, int fa = 0) {
	dep[x] = dep[fa] + 1, f[x] = fa, siz[x] = 1;
	for fec(i, x, y) if (y != fa) dfs1(y, x), siz[x] += siz[y], siz[y] > siz[son[x]] && (son[x] = y);
}
inline void dfs2(int x, int pa) {
	top[x] = pa, dfn[x] = ++dfc, pre[dfc] = x;
	if (!son[x]) return; dfs2(son[x], pa);
	for fec(i, x, y) if (y != f[x] && y != son[x]) dfs2(y, y);
}
inline int gson(int x, int p) {
	int g = 0;
	while (top[x] != top[p]) g = top[x], x = f[g];
	return x == p ? g : son[p];
}
inline bool intr(int x, int p) { return dfn[x] >= dfn[p] && dfn[x] <= dfn[p] + siz[p] - 1; }

namespace BIT {
	int s[N];
	inline void qadd(int x, int k) { for (; x <= n; x += lowbit(x)) s[x] += k; }
	inline int qsum(int x) {
		int ans = 0;
		for (; x; x -= lowbit(x)) ans += s[x];
		return ans;
	}
	inline void qadd(int l, int r, int k) { qadd(l, k), qadd(r + 1, -k); }
}
using BIT::qadd;
using BIT::qsum;

inline void solve(int L, int R, int st, int ed, int l, int r) {
	if (l > r) return;
	if (L == R) {
		for (int i = l; i <= r; ++i) *b[i].ans = L;
		return;
	}
	int M = (L + R) >> 1, n1 = 0, n2 = 0, j = l - 1;
	for (int i = st; i <= ed; ++i) {
		if (a[i].v <= M) {
			qadd(a[i].y1, a[i].y2, 1);
			q.push(std::make_pair(-a[i].x2, pii(a[i].y1, a[i].y2)));
		}
		if (i != ed && a[i].x1 == a[i + 1].x1) continue;
		
		while (j < r && (i == ed || b[j + 1].x < a[i + 1].x1)) {
			++j;
			while (!q.empty() && -q.top().fi < b[j].x) qadd(q.top().se.fi, q.top().se.se, -1), q.pop();
			int cnt = qsum(b[j].y);
			if (cnt >= b[j].k) b1[++n1] = b[j];
			else b2[++n2] = b[j], b2[n2].k -= cnt;
		}
	}
	while (!q.empty()) qadd(q.top().se.fi, q.top().se.se, -1), q.pop();
	int m1 = 0, m2 = 0;
	for (int i = st; i <= ed; ++i) if (a[i].v <= M) a1[++m1] = a[i]; else a2[++m2] = a[i];
	assert(m1 + m2 == ed - st + 1), assert(n1 + n2 == r - l + 1);
	std::copy(a1 + 1, a1 + m1 + 1, a + st), std::copy(a2 + 1, a2 + m2 + 1, a + st + m1);
	std::copy(b1 + 1, b1 + n1 + 1, b + l), std::copy(b2 + 1, b2 + n2 + 1, b + l + n1);
	solve(L, M, st, st + m1 - 1, l, l + n1 - 1), solve(M + 1, R, st + m1, ed, l + n1, r);
}

inline void work() {
	std::sort(a + 1, a + cnt + 1);
	std::sort(b + 1, b + Q + 1);
	solve(0, 1e9, 1, cnt, 1, Q);
	for (int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);
}

inline void init() {
	read(n), read(m), read(Q);
	int x, y;
	for (int i = 1; i < n; ++i) read(x), read(y), adde(x, y);
	dfs1(1), dfs2(1, 1);
	for (int i = 1; i <= m; ++i) {
		int x, y, k;
		read(x), read(y), read(k);
		assert(x != y);
		if (dfn[x] > dfn[y]) std::swap(x, y); 
		if (intr(y, x)) {
			x = gson(y, x);
			if (dfn[x] > 1) a[++cnt] = (Matrix){ 1, dfn[x] - 1, dfn[y], dfn[y] + siz[y] - 1, k };
			if (dfn[x] + siz[x] - 1 < n) a[++cnt] = (Matrix){ dfn[y], dfn[y] + siz[y] - 1, dfn[x] + siz[x], n, k };
		} else a[++cnt] = (Matrix){ dfn[x], dfn[x] + siz[x] - 1, dfn[y], dfn[y] + siz[y] - 1, k };
	}
	for (int i = 1; i <= Q; ++i) {
		int x, y, k;
		read(x), read(y), read(k);
		if (dfn[x] > dfn[y]) std::swap(x, y);
		b[i] = (Point){ dfn[x], dfn[y], k, ans + i };
	}
}

int main() {
#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
#endif
	init();
	work();
	fclose(stdin), fclose(stdout);
	return 0;
}