luoguP2441 角色属性树

暴力出奇迹

角色属性树

1. 第一眼看过去想的是分解质因数后建图处理，一看 $a \le 2^{31} - 1$ 完蛋

再仔细端详了一下数据， $n \le 2 \times 10^5$ ，估计是 $O(n \log n)$ 的算法， $\text{修改次数} \le 50$ 似乎在提示我们暴力修改，估计是个树上倍增的算法，但具体实现还没想好，就被说明/提示的最后一行吸引：本题测试数据随机，可能是假题，随机生成，也就是说……暴力的期望复杂度也是 $O(n \log n)$ ，本着能偷懒就偷懒的心态，含泪AC了

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
int w[N], fa[N];
int gcd(int x, int y)
{
	return y == 0 ? x : gcd(y, x % y);
}
int ask(int x, int a)
{
	if (x == 0)
		return -1;
	if (gcd(w[x], a) != 1)
		return x;
	return ask(fa[x], a);
}
int main()
{
	int k, op, u;
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &w[i]);
	for (int i = 1, x, y; i < n; ++i)
		scanf("%d%d", &x, &y), fa[y] = x;
	while (k--)
	{
		scanf("%d%d", &op, &u);
		if (op == 1)
			printf("%d\n", ask(fa[u], w[u]));
		else
			scanf("%d", &w[u]);
	}
	return 0;
}

后来看题解，也有树上倍增lca的做法，但是那样要维护区间乘积了，需要打高精，直接放弃