HDU6203 ping ping ping

ping，ping，ping，ping，ping

题目大意是给了你一棵 $n$ 个点的树，然后有 $m$ 对点 $(u,v)$，表示 $u$ 到 $v$ 路径上至少有一个点是不彳亍的。求最少可能有多少个不彳亍的点。

考虑贪心，我们肯定选择 $u,v$ 的 $lca$ 作为那个不彳亍的点。然而这样会有问题。

如上图，假设有两对点 $(3,5),(2,4)$，那么我们就会先把 $3,5$ 的 $lca 1$ 设置为不彳亍的点。但是之后又把 $(2,4)$ 的 $lca$ $2$ 设置为了不彳亍的点，而 $2$ 也是 $3,5$ 路径上的点，这就导致之前把 $1$ 设为不彳亍的点是浪费的。

但稍加思考可以发现，只要先处理 $lca$ 深度大的点对，再处理深度小的就不会出现这种问题，只需要用线段树判断一下路径上是否已经有不彳亍的点即可。

怎么判断呢，每次把 $lca$ 的子树全部标记，判断只需要看点对中的两个点是否被标记即可，这里就可以线段树+dfs序了。

#include <cstdio>
#include <vector>
#include <algorithm>

int fa[10005][20], dep[100005], In[10005], Out[10005], n, m, cnt;
std::vector<int> G[10005];
void dfs(int u) {
	In[u] = ++ cnt;
	for (int i = 1; i <= 18; ++ i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int v : G[u])
		if (v != fa[u][0]) fa[v][0] = u, dep[v] = dep[u] + 1, dfs(v);
	Out[u] = cnt;
}
int LCA(int u, int v) {
	if (dep[u] < dep[v]) u ^= v ^= u ^= v;
	int hhh = dep[u] - dep[v];
	for (int i = 0; i <= 18; ++ i)
		if (hhh & 1 << i) u = fa[u][i];
	if (u == v) return u;
	for (int i = 18; i >= 0; -- i)
		if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
struct Quest {
	int u, v, lca;
	inline bool operator < (const Quest a) {
		return dep[lca] > dep[a.lca];
	}
} q[50005];
struct Node {
	int l, r, v;
} tree[40005];
void make_tree(int O, int L, int R) {
	tree[O].l = L, tree[O].r = R, tree[O].v = 0;
	if (L != R) {
		make_tree(O << 1, L, L + R >> 1);
		make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
	}
}
void update(int O, int L, int R) {
	if (L <= tree[O].l && tree[O].r <= R) {
		tree[O].v = 1; return;
	}
	int mid = tree[O].l + tree[O].r >> 1;
	if (L <= mid) update(O << 1, L, R);
	if (mid < R) update(O << 1 | 1, L, R);
	tree[O].v = tree[O << 1].v & tree[O << 1 | 1].v;
}
int query(int O, int x) {
	if (tree[O].v) return 1;
	if (tree[O].l == tree[O].r) return tree[O].v;
	int mid = tree[O].l + tree[O].r >> 1;
	if (x <= mid) return query(O << 1, x);
	else return query(O << 1 | 1, x);
}

int main() {
	while (scanf("%d", &n) == 1) {
		++ n;
		make_tree(1, 1, n);
		cnt = 0;
		int ans = 0;
		for (int i = 1; i <= n; ++ i) G[i].clear();
		for (int i = 1; i < n; ++ i) {
			int u, v;
			scanf("%d%d", &u, &v);
			++ u, ++ v;
			G[u].push_back(v), G[v].push_back(u);
		}
		dfs(1);
		scanf("%d", &m);
		for (int i = 1; i <= m; ++ i)
			scanf("%d%d", &q[i].u, &q[i].v), q[i].lca = LCA(++ q[i].u, ++ q[i].v);
		std::sort(q + 1, q + m + 1);
		for (int i = 1; i <= m; ++ i) {
			if (query(1, In[q[i].u]) || query(1, In[q[i].v])) continue;
			else ++ ans, update(1, In[q[i].lca], Out[q[i].lca]);
		}
		printf("%d\n", ans);
	}
	return 0;
}