CF842C Ilya And The Tree

思路：

1. 如果根节点是0，那么可以通过一次dfs计算出所有节点的最大值。

2. 如果根节点不是0，那么其余各点的最大值一定是根节点的一个因子。首先计算出根节点的所有因子。在dfs到一个深度为d的节点v时，遍历所有因子：对于因子x，p表示从根节点到达v的路径中能够被x整除的节点个数。如果p >= d - 1，则x就是当前节点的一个候选最大值（d-1是因为可以把路径中其中一个数替换为0）。

于是通过两次dfs即可得出答案。复杂度O(n * sqrt(n))。在dfs的过程中，要注意维护全局变量。dfs到下一个分支时，要把上一个分支对全局变量造成的影响消除。

实现：

 #include <bits/stdc++.h>

 using namespace std;

 int a[], val[];

 vector<int> tree[];

 int vis[];

 int divisors[];

 void dfs(int cur, int div)

 {

     vis[cur] = ;

     for (int i = ; i < tree[cur].size(); i++)

     {

         int tmp = tree[cur][i];

         if (vis[tmp]) continue;

         val[tmp] = __gcd(div, a[tmp]);

         dfs(tmp, val[tmp]);

     }

 }

 void dfs2(int cur, int d, vector<int>& v)

 {

     vis[cur] = ;

     for (int i = ; i < tree[cur].size(); i++)

     {

         int tmp = tree[cur][i];

         if (vis[tmp]) continue;

          for (int j = ; j < v.size(); j++)

         {

             if (a[tmp] % v[j] == ) divisors[j]++;

             if (divisors[j] >= d) val[tmp] = max(val[tmp], v[j]);

         }

         dfs2(tmp, d + , v);

         for (int j = ; j < v.size(); j++)

             if (a[tmp] % v[j] == ) divisors[j]--;

     }

 }

 int main()

 {

     int n, x, y;

     while (cin >> n)

     {

         for (int i = ; i <= n; i++)

             tree[i].clear();

         for (int i = ; i <= n; i++)

             cin >> a[i];

         for (int i = ; i < n - ; i++)

         {

             cin >> x >> y;

             tree[x].push_back(y);

             tree[y].push_back(x);

         }

         int tmp = a[];

         a[] = ;

         memset(vis, , sizeof vis);

         dfs(, );

         a[] = val[] = tmp;

         vector<int> v;

         for (int i = ; i * i <= a[]; i++)

         {

             if (a[] % i == )

             {

                 v.push_back(i);

                 if (a[] / i != i) v.push_back(a[] / i);

             }

         }

         sort(v.begin(), v.end());

         for (int i = ; i < v.size(); i++) divisors[i] = ;

         memset(vis, , sizeof vis);

         dfs2(, , v);

         for (int i = ; i <= n; i++)

             cout << val[i] << " ";

         cout << endl;

     }

     return ;

 }

巴特西

CF842C Ilya And The Tree

最新文章

热门文章