[CF842C] Ilya And The Tree
Description
有一个n个节点的数,每个点有一个点权,根到这个点的所有点权(包括这个点和根)的gcd值为这个点的答案,对于每一个点的答案,你可以删除其到根节点的路径上的至多一个点来使答案最大,求每个点的答案
Solution
我们对于每个点,维护他到根的路径上所有数构成的多重集中,最多去掉一个数,形成的若干个子集的所有 gcd 的可能值
这个值的数量较小,可以用 set 暴力维护
然后我们做一个类似递推的过程,对每个点计算出这个可能值的集合即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n;
vector<int> g[N];
int a[N];
set<int> f[N];
void dfs(int p, int from, int last)
{
f[p].insert(last);
f[p].insert(__gcd(last, a[p]));
for (auto i : f[from])
f[p].insert(__gcd(i, a[p]));
for (auto q : g[p])
if (q != from)
dfs(q, p, __gcd(last, a[p]));
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0, 0);
for (int i = 1; i <= n; i++)
{
cout << *f[i].rbegin() << " ";
}
}