Codeforces 842C--Ilya And The Tree(dfs+树)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

原题链接：http://codeforces.com/contest/842/problem/C

题意：一个以1为根节点的树，每个节点有一个值a _i ，定义美丽度：从根节点到这个节点的路径上所有a _i 的gcd，即gcd(a ₁ ,a ₂ ,a ₅ ...a _i )，对每个节点的美丽度，我们可以使根到这个节点的路径上一个点的a _i 值变为0。求所有点的最大美丽度。

思路：先求出没有节点变为0的情况g[i]，在此基础上，如果使x节点变为0，那么它的美丽度为父节点的g[i]；假设让其他在路径上的点变为0，可以知道x节点的最大美丽度是a[x]的因子，因此我们只要枚举a[x]的因子，如果这个因子在路径上出现了（深度-1）次，即我们可以把路径上其中一个a[i]变为0，剩下的a[]值都含有上述因子，那么最大美丽度一定不小于这个因子。按这个方法跑一遍dfs就行了。

AC代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<map>

 using namespace std;

 const int MAXN=2e5+;

 int num[MAXN],res[MAXN],mp[MAXN],g[MAXN];

 vector<int> edge[MAXN];

 bool vis[MAXN];

 int gcd(int a, int b){

     return (b==)?a:gcd(b, a%b);

 }

 void dfs(int fa, int depth){

     int l=edge[fa].size();

     int u,k;

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

     {

         u=edge[fa][i];

         k=num[u];

         if(!vis[u]){

             vis[u]=;

             g[u]=gcd(k, g[fa]);

             res[u]=g[fa];

             for(int j=;j*j<=k;j++){

                 if(k%j==){

                     mp[j]++;

                     if(mp[j]>=depth-)    res[u]=max(res[u], j);

                     if(j*j!=k){

                         int t=k/j;

                         mp[t]++;

                         if(mp[t]>=depth-)    res[u]=max(res[u], t);

                     }

                 }

             }

             dfs(u, depth+);

             for(int j=;j*j<=k;j++){

                 if(k%j==){

                     mp[j]--;

                     if(j*j!=k) mp[k/j]--;

                 }

             }

         }

     }

     return;

 }

 int main()

 {

     int n;

     memset(vis, , sizeof(vis));

     scanf("%d", &n);

     for(int i=;i<=n;i++)    scanf("%d", &num[i]);

     int a,b;

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

         scanf("%d %d", &a, &b);

         edge[a].push_back(b);

         edge[b].push_back(a);

     }

     vis[]=;

     res[]=num[];

     g[]=num[];

     memset(mp, , sizeof(mp));

     for(int j=;j*j<=num[];j++){

         if(num[]%j==){

             mp[j]++;

             if(j*j!=num[])

                 mp[num[]/j]++;

         }

     }

     dfs(, );

     printf("%d", res[]);

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

         printf(" %d", res[i]);

     printf("\n");

 }