洛谷P2441 角色属性树题解

题意：

绪萌同人社是一个有趣的组织，该组织结构是一个树形结构。有一个社长，直接下属一些副社长。每个副社长又直接下属一些部长……。

每个成员都有一个萌点的属性，萌点属性是由一些质数的萌元素乘积构成（例如，猫耳的值是 $2$，弱气的值是 $3$，黄毛的值是 $5$，病娇的值是 $7$，双马尾的值是 $11$ 等等）

举个例子，正妹是双份的猫耳，而且有一份弱气，她的属性值为 $2\times 2\times 3=12$。

现在组员关心一个问题，希望知道离自己最近且有相同萌元素上司是谁，例如，属性值为 $2、4、6、45$ 这样的属性值都算是和正妹有相同的属性。

然而，组员可能会随时变化自己的属性。啊。。感觉好麻烦啊。。

输入格式：

第一行，$n,k$ 表示成员数与询问的次数

第二行，$n$ 个数，分别是 $1$ 到 $n$ 号成员的属性值

接下来 $n-1$ 行，$x_i,y_i$ 表示 $x_i$ 是 $y_i$ 的上司。

接下来来 $k$ 行，有两种情况

$1\ u_i$：询问离 $u_i$ 成员最近且有相同萌元素上司。

$2\ u_i$：$a$ 更改 $u_i$ 的属性值为 $a$。

输出格式：

对于每个 $1$ 类型的询问，输出符合要求的编号。如果没有符合要求的编号，输出 $-1$。

数据范围：

本题测试数据随机，可能是假题。

对于 $100\%$ 的数据，$n\le 200000$，$k<100000$，修改次数 $\le 50,a_i\le 2^{31}-1$

前置知识：欧拉乘积公式

$\zeta(z)=\prod_{p \in \mathbb{P}} \frac{1}{1-p^{-z}}$

考虑两个自然数 $a,b$ 互质的概率。

如果 $a,b$ 互质，则 $a,b$ 没有公约数 $2,3,5,\cdots$ ，即

$\left(1 - \frac{1}{2}\times \frac{1}{2}\right)\times \left(1 - \frac{1}{3}\times \frac{1}{3}\right) \times \left(1- \frac{1}{5}\times \frac{1}{5}\right)\times \cdots$

整理一下可得

$\prod_{p \in \mathbb{P}}(1-p^{-2}) = \frac{1}{\zeta(2)}$

而众所周知 $\zeta(2)=\frac{\pi^2}{6}$ ，概率即为 $\frac{6}{\pi^2}\approx0.6079271$ 。

于是两个自然数不互质的概率为 $p = 1 - \frac{6}{\pi^2} \approx 0.392$

对于本题，暴力 $k$ 次询问得到答案的概率为 $f(k)=\sum_{0 \le i < k}(1-p)^ip$

计算可知在 $k = 10$ 时 $f(k)\approx0.993105$ ，这已经是非常高的概率了。

因为数据是随机的，所以暴力的复杂度为 $\mathcal{O}(q\log n)$ ，这里的 $\log n$ 是树高

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

int n,q,a[N],fa[N];
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int dfs(int x, int y)
{
    if(x == 0) return -1;
    if(gcd(a[x], a[y]) > 1) return x;
    return dfs(fa[x], y);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1, x, y; i < n; i++) { cin >> x >> y; fa[y] = x; }
    for(int i = 1, x, y; i <= q; i++)
    {
        cin >> x;
        if(x == 1) {
            cin >> y; cout << dfs(fa[y], y) << '\n';
        }else { cin >> x >> y; a[x] = y; }
    }
    return 0;
}