题目链接
题意: 有一个树，树上的每个点都有一个权值，对于一个点的魅力值来说，是他到根点1的路径上的所有点权值的最大公约数，对于每个路径上的点，你可以选择唯一点将他变为0或者不做改变，现在希望你让每个点都获得尽可能大的魅力值，输出每个点的魅力值
思路:
这个题目大概是需要在树上做个dp吧,但是我们知道所有的dp都可以由搜索的状态转移而来,所以我们可以先考虑搜索的状态。
首先要有x,表示当前搜索到哪个结点,还要有gcd,表示从根节点到当前路径的gcd是多少,还需要一个flag,表示从根节点到当前路径是否把一个点变为0。为了不重复走点,再加一个f,表示此节点的父节点.
那么我们对每一个都有两种搜索状态,一种是舍弃该点,那么需要接着父亲的gcd，并把flag变1往下搜索,另一种是不舍弃该点,两个过程维护最大值。
小优化: 如果该点以上已经修改过了,或者修不修改gcd不变，则不需要舍弃该点.
另外,由于我们从根节点往下gcd是只减不增的,一直往下搜索的时候,到了有些点就没必要搜索下去了,而且每个点最多只走两次,所以复杂度是线性的. O(2n)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; const int maxn=2e5+10; int n; int a[maxn]; vector<vector<int> >vt(maxn); int ans[maxn]; void dfs(int x,int f,int gcd,bool flag) { int g; if(gcd) g = __gcd(gcd,a[x]); else g = a[x]; ans[x] = max(ans[x],g);//不去掉此节点 for(int i=0;i<vt[x].size();i++) { int v = vt[x][i]; if(v==f) continue; dfs(v,x,g,flag); } if(flag || g == gcd) return ;//剪枝,如果已经使用一次了则无法再用,或者改变之后gcd无变化,则应节省. ans[x] = max(ans[x],gcd);//把此节点去掉 for(int i=0;i<vt[x].size();i++) { int v = vt[x][i]; if(v==f) continue; dfs(v,x,gcd,true); } return ; } int main(){ cin>>n; memset(ans,0,sizeof ans); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int x,y; for(int i=1;i<n;i++) { scanf("%d %d",&x,&y); vt[x].push_back(y); vt[y].push_back(x); } dfs(1,-1,0,0); for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' '); return 0; }
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
