角色属性树

archer233 / 2024-10-23 / 原文

原题链接
题目大意：
$对一颗树上的节点的最近有相同因数的上司$
$需要做到维护和修改两种操作$

$idea：直接做即可因为给出的数据随机虽然在最坏情况下会达到n*k但是根据数学期望 gcd(a,b)>1在经过一系列小学计算得出期望约为O(klogn)$
$注意：因为要迭代父亲所以需要反向建树$
$code:$

点击查看代码

#include<bits/stdc++.h>

#define int long long
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int mod=1e9+7;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
void solve() {
    int n,k;cin>>n>>k;
    vector G(n+1,vector<int>());
    vector<int>val(n+1);
    for(int i=1;i<=n;i++)cin>>val[i];
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        G[y].pb(x);
    }
    function<int(int,int)>dfs=[&](int x,int now){
        for(auto &fa:G[x]){
            if(gcd(val[fa],val[now])>1){
                return fa;
            }
            return dfs(fa,now);
        }
        return -1ll;
    };
    while(k--){
        int op;
        cin>>op;
        if(op==1){
            int u;cin>>u;
            int ans=dfs(u,u);
            cout<<ans<<'\n';
        }else {
            int u,x;cin>>u>>x;
            val[u]=x;
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int _=1;
//    cin>>_;
    while(_--)solve();
}