最长树链

题意: 给出一颗树，请你找出最长的一条链，这条链上所有数值的GCD要大于1.并输出最长链的长度。

这题参考了 小熠小熠很不容易 大佬的思路。

思路就是，先建一棵树，然后从根开始搜索，这里要注意根不一定是1,要自己找根。

然后再搜索的时候，每次计算下GCD，如果GCD大于1，那么是满足条件的，我们继续往下搜索。如果等于1，那么说明当前长度不能继续变长了，我们就重置这个树链长度为1.

这种思路应该非常好理解的，就相当于暴力的搜索下去，边搜边记录答案即可。

还有一种求质因子的方式本弱还没弄明白。。。。

AC代码:

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=100000+100;
int n,x,y,ans;
int a[N],f[N];
vector<int>v[N];
void dfs(int u,int len,int w)
{
    for(auto x:v[u])
    {
        int gc=__gcd(a[x],w);
        if(gc==1)
        {
            ans=max(ans,len);
            dfs(x,1,a[x]);
        }
        else
        {
            ans=max(ans,len+1);
            dfs(x,len+1,gc);
        }
    }

}
signed main()
{
    scanf("%lld",&n);
    for(int i=0;i<n-1;i++)
    {
        scanf("%lld%lld",&x,&y);
        v[x].push_back(y);
        f[y]=1;
    }
    int root=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(!f[i]&&!root)root=i;
    }
    dfs(root,1,a[root]);
    printf("%lld\n",ans);
    return 0;
}