Luogu T273083 新的题目 题解

怕放洛谷有人看，就搬过来了。

本题解提供一个 \(O(qn)\) 的做法（实际上是暴力的优化）。

先考虑暴力求解。

对于每个操作，要求代价 \(W \times (\sum_{i \in X}^{i} w[i] \times dis[i][x] + \sum_{j \in Y}^{j} w[j] \times dis[j][y])\)，我们需要对每个 \(i\) 或 \(j\) 都求一遍 \(dis[i][x]\) 或 \(dis[j][y]\)。而这个过程大约是 \(O(n)\) 的。加上每次操作最多有 \(n\) 个点，时间复杂度 \(O(qn^2)\)。

这个复杂度显然是不能接受的。因此考虑如何优化。

操作的点数和总操作数是无法优化的，所以我们尝试对求 \(dis\) 的过程优化。

如果在树上有一个定点 \(x\)，我们可以以它为根进行 dfs，这样可以在 \(O(n)\) 时间内求出所有其它点的“深度”，也就是我们要的 \(dis\)。

因为树上任意两点间的路径有且只有一条，进行操作只会使原本有的路径消失而不会增加新的路径。

那么我们就能够直接在进行操作前对于每个 \(i \in [1, n]\) 进行 dfs，预处理出树上任意两点间的距离。预处理复杂度 \(O(n^2)\)，需要时 \(O(1)\) 查表即可。

于是我们优化掉了 \(O(n)\) 的复杂度，剩下 \(O(qn)\)，足以通过 \(n,q \le 5 \times 10^3\) 的数据。

注意到毒瘤出题人（我不说是谁）卡了本题的空间，实现时要当心。

放一个不开会 O2 T 飞的屑代码。

Code

#include <bits/stdc++.h> 
using namespace std;
const int N = 5e3 + 10;
map <pair<int, int>, bool> mp1;
map <pair<int, int>, int> mp2;
int dis[N][N], w[N];
struct node
{
	int to, next, value;
}e[N << 1];
int head[N];
bool vis[N];
int tot;
long long res, ans;
inline int read()
{
	register int r = 0, c = getchar(), f = 1;
	while (c < '0' || c > '9')
	{
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') r = (r << 3) + (r << 1) + (c ^ 48), c = getchar();
	return r * f;
}
inline void add(int u, int v, int w)
{
	e[++tot].to = v;
	e[tot].value = w;
	e[tot].next = head[u];
	mp2[{u, v}] = w;
	head[u] = tot;
}
void dfs(int now, int rt)
{
	vis[now] = 1;
	for (int i = head[now]; i; i = e[i].next)
	{
		int y = e[i].to;
		if (!vis[y]) 
		{
			dis[y][rt] = dis[now][rt] + e[i].value;
			dfs(y, rt);
		}
	}
}
void dfs2(int now, int rt)
{
	vis[now] = 1;
	res += w[now] * 1ll * dis[now][rt];
	for (int i = head[now]; i; i = e[i].next)
	{
		register int y = e[i].to;
		if (!mp1[{now, y}] && !vis[y]) dfs2(y, rt);
	}
}
int main()
{
	register int n = read();
	for (register int i = 1; i <= n; ++i) w[i] = read();
	for (register int i = 1; i < n; ++i) 
	{
		register int x = read(), y = read(), z = read();
		add(x, y, z);
		add(y, x, z);
	}
	for (register int i = 1; i <= n; ++i) 
	{
		memset(vis, 0, sizeof vis);
		dfs(i, i);
	}
//	for (int i = 1; i <= n; ++i) 
//	{
//		for (int j = 1; j <= n; ++j) printf("%d ", dis[i][j]);
//		puts(""); 
//	}
	register int q = read();
	while (q--)
	{
		res = 0;
		register int u = read(), v = read();
		mp1[{u, v}] = mp1[{v, u}] = 1;
		memset(vis, 0, sizeof vis);
		dfs2(u, u);
		memset(vis, 0, sizeof vis);
		dfs2(v, v);
//		printf("\n%d\n", res);
		res *= mp2[{u, v}];
		ans ^= res;
	}
	printf("%lld\n", ans);
	return 0;
}