牛客 最長樹鍊 圖

最長樹鍊

題目連結

這道題讓我明白了運氣是實力的一部分

暴力出奇迹

題目大意：

給一棵樹 讓求最長的樹鍊: 傻逼，這不就樹的直徑嗎

給每個點權值，找出的鍊要滿足鍊上的點的權值的 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);
}