题解P2441 角色属性树

Zilljy258 · 2022-06-07 19:44:25 · 题解

暴力：编程界最热门的算法。

题目传送门

大体思路：

建一棵树，对于每次询问暴力搜索，对于每次更改进行实时的更改。

怎么暴力搜索？

其实“两个成员有相同的属性”说白了就是“两个成员的属性值的 \gcd(a_x,a_y) > 1”

所以只要顺着 father 数组顺藤摸瓜，一个一个的枚举上司的属性值问题就解决了。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[200001]={0};
int fa[200001]={0};  // father 数组
int dfs(int x,int y){     //搜索。
    if(x == 0) return -1;
    if(__gcd(a[x],a[y]) > 1) return x;  //偷一下懒~直接使用gcd函数。
    return dfs(fa[x],y);
}
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        fa[y]=x;  //建树
    }
    for(int i=1;i<=k;i++){
        int x,y;
        cin>>x;
        if(x==1){
            cin>>y;
            cout<<dfs(fa[y],y)<<endl;  //搜索
        }
        else{
            cin>>x>>y;
            a[x]=y;
        }
    } 
    return 0;
} 

总结：

学好暴力很重要。

此题并不难，注意枚举和建树就好了。

后记：这是萌新第二次写题解，可能有不足之处，如果大家有要我补充的或改进的，一定要提出来！谢谢大家。