newcoder-最长树链-树/gcd
https://ac.nowcoder.com/acm/problem/13233
链接：https://ac.nowcoder.com/acm/problem/13233
来源：牛客网
题目描述
树链是指树里的一条路径。美团外卖的形象代言人袋鼠先生最近在研究一个特殊的最长树链问题。现在树中的每个点都有一个正整数值，他想在树中找出最长的树链，使得这条树链上所有对应点的值的最大公约数大于1。请求出这条树链的长度。输入描述:
第1行：整数n（1 ≤ n ≤ 100000），表示点的个数。
第2~n行：每行两个整数x，y表示xy之间有边，数据保证给出的是一棵树。
第n+1行：n个整数，依次表示点1~n对应的权值（1 ≤ 权值 ≤ 1,000,000,000）。
输出描述:
满足最长路径的长度
示例1
输入
复制4
1 2
1 3
2 4
6 4 5 2
输出
复制3
这条链的gcd>1,反过来说就是对于链上每个点，都可以写成k*p的形式，p就是他们的最大公约数，显然满足k*p也一定
满足k*pi(p%pi==0).所以可以以质因子对节点进行分类，具有相同质因子的点分在一类，对每一类点跑一次最长链即可。
每个点被访问次数就是他的质因子个数，复杂度大约就是N*log(N)。
1 #include<bits/stdc++.h>
2 using namespace std; 3 #define LL long long
4 unordered_map<int,vector<int> >g; 5 const int maxn=100010; 6 int n,val[maxn]; 7 bool vis[maxn]; 8 vector<int>e[maxn]; 9 int dfs(int u,int p){ 10 vis[u]=1; 11 int m1=0,m2=0; 12 for(auto v:e[u]){ 13 if(vis[v] || val[v]%p!=0)continue; 14 int d=dfs(v,p); 15 if(d>m1) { 16 m2=m1; 17 m1=d; 18 } 19 else if(d>m2){ 20 m2=d; 21 } 22 } 23 return m1+m2+1; 24 } 25 int solve(int u){ 26 int res=0; 27 for(auto x:g[u]){ 28 if(!vis[x]){ 29 res=max(res,dfs(x,u)); 30 } 31 } 32 for(auto x:g[u]){ 33 vis[x]=0; 34 } 35 return res; 36 } 37 int main(){ 38 int u,v; 39 cin>>n; 40 for(int i=1;i<n;++i){ 41 scanf("%d%d",&u,&v); 42 e[u].push_back(v); 43 e[v].push_back(u); 44 } 45 for(int i=1;i<=n;++i){ 46 scanf("%d",val+i); 47 int x=val[i]; 48 for(int v=2;v*v<=x;v++){ 49 if(x%v==0){ 50 while(x%v==0)x/=v; 51 g[v].push_back(i); 52 } 53 } 54 if(x>1){ 55 g[x].push_back(i); 56 } 57 } 58
59 int ans=0; 60 for(auto i:g){ 61 ans=max(ans,solve(i.first)); 62 } 63 cout<<ans; 64 return 0; 65 }
更多精彩
