洛谷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;
}