NC13233. 最长树链
描述
输入描述
第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
C++(clang++11) 解法, 执行用时: 76ms, 内存消耗: 10488K, 提交时间: 2021-01-14 10:11:52
#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)dfs(x,1,a[x]);
else dfs(x,len+1,gc);
}
ans=max(ans,len);
}
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;
}