P3242 [HNOI2015] 接水果

整体二分练手题。

考虑一条路径 \((x,y)\) 被另一条路径 \((u,v)\) 包含的本质。

考虑 dfs 序，设 \(st_x=dfn_x\)，$$ed_x=dfn_x+siz_x-1$。

不妨设 \(st_x<st_y\)。

• \(\operatorname{LCA}(x,y)=x\)

  则 \(u\in [1,st_z-1]\) 或 \(u \in[ed_z+1,n]\)，\(v \in [st_y,ed_y]\)，其中 \(z\) 为 \(x \to y\) 路径上 \(x\) 的第一个儿子。

• \(LCA(x,y) \ne x\)

  则 \(u\in [st_x,ed_x]\)，\(v \in [st_y,ed_y]\)。

由于题目查询第 \(k\) 大，考虑整体二分。

整体二分加扫描线，时间复杂度 \(\mathcal O(n \log^2 n)\)，空间复杂度 \(\mathcal O(n)\)。

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

const int _ = 4e4 + 10;

int n, m, Q, B, ans[_];

int len, mp[_];

int tot, head[_], to[_ << 1], nxt[_ << 1];

inline void add(int u, int v)
{
	to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}

int cnt, dep[_], siz[_], fa[_], top[_], hson[_], st[_], ed[_];

struct Query
{
	int op, x, l, r, k, v, id;
} q[_ * 5], q1[_ * 5], q2[_ * 5];

inline bool cmp(Query a, Query b)
{
	if(a.x != b.x) return a.x < b.x;
	return a.op < b.op;
}

void dfs1(int u, int D = 1)
{
	dep[u] = D, siz[u] = 1;
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(siz[v]) continue;
		fa[v] = u;
		dfs1(v, D + 1);
		siz[u] += siz[v];
		if(siz[hson[u]] < siz[v]) hson[u] = v;
	}
}

void dfs2(int u, int tf)
{
	top[u] = tf;
	st[u] = ++cnt;
	if(hson[u]) dfs2(hson[u], tf);
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(top[v]) continue;
		dfs2(v, v);
	}
	ed[u] = cnt;
}

inline int LCA(int x, int y)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		x = fa[top[x]];
	}
	return dep[x] > dep[y] ? y : x;
}

inline int get(int x, int y)
{
	while(top[x] != top[y])
	{
		if(fa[top[x]] == y) return top[x];
		x = fa[top[x]];
	}
	return hson[y];
}

int c[_];

inline void update(int x, int y)
{
	for(; x <= n; x += x & -x) c[x] += y;
}

inline int query(int x)
{
	int res = 0;
	for(; x; x -= x & -x) res += c[x];
	return res;
}

void solve(int L, int R, int l, int r)
{
	if(L > R) return;
	if(l == r)
	{
		for(int i = L; i <= R; ++i)
			if(q[i].op == 2) ans[q[i].id] = mp[l];
		return;
	}
	int mid = (l + r) >> 1, c1 = 0, c2 = 0, val;
	for(int i = L; i <= R; ++i)
		if(q[i].op == 1)
		{
			if(q[i].k <= mid)
			{
				update(q[i].l, q[i].v), update(q[i].r + 1, -q[i].v);
				q1[++c1] = q[i];
			}
			else q2[++c2] = q[i];
		}
		else
		{
			val = query(q[i].l);
			if(val >= q[i].k) q1[++c1] = q[i];
			else q[i].k -= val, q2[++c2] = q[i];
		}
	for(int i = 1; i <= c1; ++i) q[L + i - 1] = q1[i];
	for(int i = 1; i <= c2; ++i) q[L + i + c1 - 1] = q2[i];
	solve(L, L + c1 - 1, l, mid), solve(L + c1, R, mid + 1, r);
}

signed main()
{
	n = read(), m = read(), Q = read();
	for(int i = 1, x, y; i < n; ++i)
	{
		x = read(), y = read();
		add(x, y), add(y, x);
	}
	dfs1(1), dfs2(1, 1);
	for(int i = 1, x, y, z, k, lca; i <= m; ++i)
	{
		x = read(), y = read(), k = read();
		mp[i] = k;
		if(st[x] > st[y]) swap(x, y);
		lca = LCA(x, y);
		if(lca == x)
		{
			z = get(y, x);
			if(st[z] > 1)
			{
				q[++B] = {1, 1, st[y], ed[y], k, 1, 0};
				q[++B] = {1, st[z], st[y], ed[y], k, -1, 0};
			}
			if(ed[z] < n)
			{
				q[++B] = {1, st[y], ed[z] + 1, n, k, 1, 0};
				q[++B] = {1, ed[y] + 1, ed[z] + 1, n, k, -1, 0};
			}
		}
		else
		{
			q[++B] = {1, st[x], st[y], ed[y], k, 1, 0};
			q[++B] = {1, ed[x] + 1, st[y], ed[y], k, -1, 0};
		}
	}
	sort(mp + 1, mp + m + 1);
	len = unique(mp + 1, mp + m + 1) - mp - 1;
	for(int i = 1; i <= B; ++i) q[i].k = lower_bound(mp + 1, mp + len + 1, q[i].k) - mp;
	for(int i = 1, x, y, k; i <= Q; ++i)
	{
		x = read(), y = read(), k = read();
		if(st[x] > st[y]) swap(x, y);
		q[++B] = {2, st[x], st[y], 0, k, 0, i};
	}
	sort(q + 1, q + B + 1, cmp);
	solve(1, B, 1, len);
	for(int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);
	return 0;
}