最长树链

题目链接
这道题让我明白了运气是实力的一部分
暴力出奇迹

题目大意：

给一棵树 让求最长的树链: ***，这不就树的直径吗
给每个点权值，找出的链要满足链上的点的权值的 gcd > 1 然后 找一个最长的

所以怎么做呢？ 一直想不出来没想到就是暴力，怎么暴呢？就是枚举质数，但是枚举所有质数太多了，所以先找出所有点权的质因子，然后%这个质因子是0的点才能走，所以就是暴力？ 但是我还是会tle 于是加了个快读。。此时语言:c++11毫不留情的tle，加了快读但是更慢？ 于是t了几发换成了c++14直接ac？？

大佬博客说 质因数个数是log级别的 然后 枚举再跑图 就是 O(能过)的时间复杂度，
代码:

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<set>
#include<math.h>
using namespace std;
const int maxn = 1e5+5;
int val[maxn];
int vis[maxn]; 
set<int> ss;
int root;
int dep[maxn];
struct Edge
{
   
	int id,next;
}edge[maxn<<2];
int head[maxn];
int cnt = 1;
inline int read()
{
   
    int f=1,ans=0;char c;
    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){
   ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
void add(int x,int y)
{
   
	edge[cnt].id = y;
	edge[cnt].next = head[x];
	head[x] = cnt++;
	edge[cnt].id = x;
	edge[cnt].next = head[y];
	head[y] = cnt++;
}
int f;
void dfs(int x,int fa,int dp)
{
   
// printf("%d %d 1\n",x,dp);
	dep[x] = dp;
	if(dep[root] < dep[x])
		root = x;
	for (int i = head[x]; ~i; i = edge[i].next )
	{
   
		int v = edge[i].id;
		if(v == fa || vis[v] == 0)
			continue;
		if(f)
			vis[v] = 0;
		dfs(v,x,dp+1);
	} 
}
int main()
{
   
	int n;
	n = read();
	for (int i = 1; i <= n; i ++ )
	{
   
		head[i] = -1;
	}
	for(int i = 1; i < n; i ++ )
	{
   
		int x,y;
		x = read();
		y = read();
		add(x,y);
	}
	for (int  i= 1; i <= n; i ++ )
	{
   
		val[i] = read();
	}
	for(int i = 1; i <= n; i ++ )
	{
   
		int s = val[i];
		for (int j = 2; j <= sqrt(s); j ++ )
		{
   
			if(s%j == 0)
			{
   
				ss.insert(j);
				while(s%j==0)
					s/=j;
			}
		}
		if(s>1)
			ss.insert(s);
	}
	int ans = 0 ;
	set<int>::iterator it = ss.begin();
	for(; it!=ss.end(); it ++ )
	{
   
		int x = *it;
		for(int j = 1; j <= n; j ++ )
		{
   
			if(val[j]%x == 0)
			{
   
// printf("%d ",j);
				vis[j] = 1;
			}
			else
				vis[j] = 0;
		}
// printf("%d\n",x);
		for (int j = 1; j <= n; j ++ )
		{
   
			if(vis[j] == 1)
			{
   
// printf("%d\n",j);
				root = 0;
				f = 0;
				dfs(j,-1,1);
				f = 1;vis[root] = 0;
				dfs(root,-1,1);
				
				ans = max(ans,dep[root]);
			}
		}
	}
	printf("%d\n",ans);
}