P8201 [传智杯 #4 决赛] [yLOI2021] 生活在树上（hard version）

P8201 [传智杯 #4 决赛] [yLOI2021] 生活在树上（hard version）

结论+离线询问 或 结论+主席树

结论通过画图不难得出，树上任意一个点到 \(u\) 和 \(v\) 的路径的并一定包含 \(u\) 到 \(v\) 的路径，并且任意一个点到 \(u\) 和 \(v\) 的路径的重叠部分与 \(u\) 到 \(v\) 的路径有且仅有一个交点。我们也很容易构造出交点是 \(u\) 到 \(v\) 路径中某一个点的方案。

考虑答案的变化，首先重叠部分抵消，于是就权值剩下 \(u\) 到 \(v\) 的路径再扣掉交点的权值。具体的，若交点为 \(x\)，则答案为 \(dis_{u,v}\oplus w_x\)，而 \(dis_{u,v}\oplus w_x=k\) 就是 \(dis_{u,v}\oplus k=w_x\)。于是题目变成：求 \(u\) 到 \(v\) 的路径上是否存在权值为 \(w_x\) 的点。\(dis_{u,v}\) 容易预处理。

法一：

考虑统计 \(u\) 到 \(v\) 路径上每个权值的数量。将询问离线，拆成 \(u\)、\(v\)、\(\rm fa_{lca(u,v)}\) 三部分计算答案，每一部分的形式为 \(buc_{u,i}\) 表示 \(u\) 到根的路径上权值 \(i\) 的出现次数，开一个全局桶，跑一遍 dfs 就可以了。这个方法比较经典。

法二：

同样考虑维护权值数量，我们考虑对每个点建一颗权值主席树记录该点到根出现的权值数量，即可在线询问了。法二的方法比较常见。

复杂度都是 \(O(n\log n)\)，在于求 \(\rm lca\)。

法一代码：

int lca(int u, int v) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) std::swap(u, v);
	return u;
}
int buc[40000010];
void dfs(int u) {
	buc[w[u]]++;
	for(auto x : ve[u]) {
		ans[x[0]] += buc[x[1]] * x[2];
	}
	for(auto v : e[u]) {
		if(v == fa[u]) continue;
		dfs(v);
	}
	buc[w[u]]--;
}
void Solve() {
	std::cin >> n >> m;

	for(int i = 1; i <= n; i++) {
		std::cin >> w[i];
	}

	for(int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		e[u].pb(v), e[v].pb(u);
	}

	d[1] = w[1];
	dfs1(1, 0);
	dfs2(1, 1);
	for(int i = 1; i <= m; i++) {
		int a, b, k;
		std::cin >> a >> b >> k;
		int rt = lca(a, b), x = d[a] ^ d[b] ^ w[rt] ^ k;
		ve[a].pb({i, x, 1}), ve[b].pb({i, x, 1}), ve[fa[rt]].pb({i, x, -2}); //离线拆询问
	}
	dfs(1);

	for(int i = 1; i <= m; i++) {
		if(ans[i]) std::cout << "YES\n";
		else std::cout << "NO\n";	
	}
}

法二代码：

int lca(int u, int v) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) std::swap(u, v);
	return u;
}
struct seg {
	int ls, rs, v;
} t[N * 40];
void mkt(int &o, int u, int l, int r, int x) {
	o = ++tot;
	t[o] = t[u];
	if(l == r) {
		t[o].v++;
		return;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) mkt(t[o].ls, t[u].ls, l, mid, x);
	else mkt(t[o].rs, t[u].rs, mid + 1, r, x);
}
int qry(int u, int l, int r, int x) {
	if(!u) return 0;
	if(l == r) {
		return t[u].v;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) return qry(t[u].ls, l, mid, x);
	return qry(t[u].rs, mid + 1, r, x);
}
void dfs(int u) {
	for(auto v : e[u]) {
		if(v == fa[u]) continue;
		mkt(rt[v], rt[u], 1, mx, w[v]);
		dfs(v);
	}
}
void Solve() {
	std::cin >> n >> m;

	for(int i = 1; i <= n; i++) {
		std::cin >> w[i];
	}

	for(int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		e[u].pb(v), e[v].pb(u);
	}

	dfs1(1, 0);
	dfs2(1, 1);
	mkt(rt[1], rt[0], 1, mx, w[1]);
	dfs(1);
	while(m--) {
		int a, b, k;
		std::cin >> a >> b >> k;
		int rot = lca(a, b), x = d[a] ^ d[b] ^ w[rot] ^ k;
		int ret = qry(rt[a], 1, mx, x) + qry(rt[b], 1, mx, x) - 2 * qry(rt[fa[rot]], 1, mx, x);
		if(ret) std::cout << "YES\n";
		else std::cout << "NO\n";
	}
}