「CF983E」 NN country - 倍增 + 二维数点

题目链接：传送门

Description

给一棵$n$个节点的树，有$m$条路径。给出$q$组询问，每组询问$(x, y)$求出$x$到$y$的路径至少需要多少条给出的路径覆盖,可能无解

Hint

$n, m, q \leq 2 * 10^5$

Solution

首先对于一条询问的路径$(x, y)$，我们可以拆成$(x,lca)$和$(y, lca)$这两条路径

那么我们只需要考虑从一个点$x$到它的祖先$lca$至少需要多少条路径覆盖

显然这个我们可以通过倍增来实现

设$top[x][i]$表示节点$x$被$2^i$条路径覆盖，能到达的深度最浅的点，直接倍增即可

假设$x$已经倍增到了$u$节点，且$dep_{top[u][0]} \leq dep_{lca}$，感性理解就是在$lca$下面一点点的那个点，$y$已经倍增到了$v$,且总共倍增了$sum$次

那么有可能存在一条链能直接覆盖$(u, v)$ ，那么答案就是$sum+1$

如果不存在那么答案就是$sum+2$

要判断是否存在一条能覆盖$(u,v)$的链，实际上就是要求是否存在一条链，使得它的两个端点分别在$u$和$v$的子树中

那么这一部分的求解就转化成了在$dfs$序上的二维数点问题

扫描线 + 树状数组即可

$P.S.$代码居然写了4.2K。。。

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
template <typename T> T read()
{
	T fl = 1, sum = 0; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fl = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * fl;
}

const int Maxn = 2 * 1e5 + 100;

int N, M, Q;
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];
int anc[Maxn][22], top[Maxn][22], dep[Maxn], dfn[Maxn], Index, size[Maxn];
int Ans[Maxn];

inline void add_edge (int x, int y)
{
	To[++e] = y;
	Next[e] = Begin[x];
	Begin[x] = e;
}

inline void pre_dfs (int x)
{
	for (int i = 1; i <= 20; ++i) anc[x][i] = anc[anc[x][i - 1]][i - 1];
	dfn[x] = ++Index;
	size[x] = 1;
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == anc[x][0]) continue;
		anc[y][0] = x;
		dep[y] = dep[x] + 1;
		pre_dfs(y);
		size[x] += size[y];
	}
}

inline void dfs (int x)
{
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == anc[x][0]) continue;
		dfs(y);
		if (dep[top[y][0]] < dep[top[x][0]]) top[x][0] = top[y][0];
	}
}

inline int Lca (int x, int y)
{
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = 20; i >= 0; --i)
		if (dep[anc[x][i]] >= dep[y]) x = anc[x][i];
	if (x == y) return x;
	for (int i = 20; i >= 0; --i)
		if (anc[x][i] != anc[y][i])
			x = anc[x][i], y = anc[y][i];
	return anc[x][0];
}

struct query
{
	int x, y, num, type; 
};

vector <query> vec[Maxn];
vector <int> vec1[Maxn];
int FLAG[Maxn];

inline void calc (int x, int y, int nowww)
{
	int LCA = Lca(x, y), now = x, sum = 0, u, v;
	for (int i = 20; i >= 0; --i)
		if (dep[top[now][i]] > dep[LCA]) now = top[now][i], sum |= (1 << i);
	u = now;
	if (dep[top[u][0]] > dep[LCA]) { FLAG[nowww] = 1; Ans[nowww] = -1; return ; }
	now = y;
	for (int i = 20; i >= 0; --i)
		if (dep[top[now][i]] > dep[LCA]) now = top[now][i], sum += (1 << i);
	v = now;
	if (dep[top[v][0]] > dep[LCA]) { FLAG[nowww] = 1; Ans[nowww] = -1; return ; }
	if (LCA == x || LCA == y) { FLAG[nowww] = 1; Ans[nowww] = sum + 1; return ; }
	int x1 = dfn[u], x2 = dfn[u] + size[u] - 1, y1 = dfn[v], y2 = dfn[v] + size[v] - 1;
//	cout<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<endl;
	vec[x1 - 1].pb((query){y1 - 1, y2, nowww, -1}); vec[x2].pb((query){y1 - 1, y2, nowww, 1});
	Ans[nowww] = sum;
}

namespace BIT
{
	int Sum[Maxn << 1];
#define lowbit(x) (x & (-x))
	inline void add (int x, int v) { while (x <= N) Sum[x] += v, x += lowbit(x); }
	inline int query (int x) { int ans = 0; while (x) ans += Sum[x], x -= lowbit(x); return ans; }
}

int Sum[Maxn];

int main()
{
#ifdef hk_cnyali
	freopen("E.in", "r", stdin);
	freopen("E.out", "w", stdout);
#endif
	N = read<int>();
	for (int i = 2; i <= N; ++i)
	{
		int x = read<int>();
		add_edge (x, i); add_edge (i, x);
	}
	for (int i = 1; i <= N; ++i) top[i][0] = i;
	M = read<int>();
	dep[1] = 1; pre_dfs(1);
	while (M--)
	{
		int x = read<int>(), y = read<int>();
		int u = Lca(x, y);
//		cout<<x<<" "<<y<<" "<<u<<endl;
		vec1[dfn[x]].pb(dfn[y]);
		vec1[dfn[y]].pb(dfn[x]);
		if (dep[u] < dep[top[x][0]]) top[x][0] = u; //, cout<<"fuck";
		if (dep[u] < dep[top[y][0]]) top[y][0] = u; //, cout<<"fuck";
//		puts("");
	}
	dfs(1);

	for (int j = 1; j <= 20; ++j)
		for (int i = 1; i <= N; ++i)
			top[i][j] = top[top[i][j - 1]][j - 1];

	Q = read<int>();
	for (int i = 1; i <= Q; ++i)
	{
		int x = read<int>(), y = read<int>();
		calc(x, y, i);
	}

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j < vec1[i].size(); ++j)
		{
			int x = vec1[i][j];
			BIT :: add(x, 1);
		}
		for (int j = 0; j < vec[i].size(); ++j)
		{
			query x = vec[i][j];
			int sum = BIT :: query(x.y) - BIT :: query(x.x);
			Sum[x.num] += sum * x.type;
		}
	}
	
	for (int i = 1; i <= Q; ++i)
	{
		if (FLAG[i]);
		else if (Sum[i] > 0) Ans[i] ++;
		else Ans[i] += 2;
		printf("%d\n", Ans[i]);
	}

	return 0;
}

/*
注意dfn[x]和x不要搞混了。。。
*/