CF990G

题意

https://codeforces.com/contest/990/problem/G

思考

在200000以内，因数个数最多的数位166320，共有160个因数。可以知道，从一个节点向下走最多只会有160种取值。

记集合f[u]为从u节点向下走可以取得的所有值及其个数，暴力转移即可。

至于合并，博主写了平方.......但这题想造出极端数据也是困难的。

最后注意空间。

代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long int ll;
  4 const int maxn=2E5+5;
  5 const ll base=2E5+5;
  6 int n,val[maxn];
  7 int head[maxn*2],size;
  8 ll ans[maxn],wait[maxn];
  9 bool vis[maxn];
 10 inline int gcd(int x,int y)
 11 {
 12     return x%y==0?y:gcd(y,x%y);
 13 }
 14 struct edge
 15 {
 16     int to,next;
 17 }E[maxn*2];
 18 inline void add(int u,int v)
 19 {
 20     E[++size].to=v;
 21     E[size].next=head[u];
 22     head[u]=size;
 23 }
 24 struct note
 25 {
 26     int x,c;
 27     note(int a=0,int b=0)
 28     {
 29         x=a,c=b;
 30     }
 31 };
 32 queue<note>T[maxn];
 33 vector<note>t;
 34 void dfs(int u,int F)
 35 {
 36     vector<int>what;
 37     for(int i=head[u];i;i=E[i].next)
 38     {
 39         int v=E[i].to;
 40         if(v==F)
 41             continue;
 42         dfs(v,u);
 43     }
 44     for(int i=head[u];i;i=E[i].next)
 45     {
 46         int v=E[i].to;
 47         if(v==F)
 48             continue;
 49         t.clear();
 50         while(!T[v].empty())
 51         {
 52             t.push_back(T[v].front());
 53             T[v].pop();
 54         }
 55         for(int j=0;j<what.size();++j)
 56         {
 57             int x=what[j];
 58             for(int k=0;k<t.size();++k)
 59                 ans[gcd(x,t[k].x)]+=wait[x]*t[k].c;
 60         }
 61         for(int j=0;j<t.size();++j)
 62         {
 63             int x=gcd(val[u],t[j].x);
 64             if(!vis[x])
 65             {
 66                 vis[x]=1;
 67                 wait[x]=t[j].c;
 68                 what.push_back(x);
 69             }
 70             else
 71                 wait[x]+=t[j].c;
 72         }
 73     }
 74     if(!vis[val[u]])
 75     {
 76         vis[val[u]]=1;
 77         wait[val[u]]=1;
 78         what.push_back(val[u]);
 79     }
 80     else
 81         ++wait[val[u]];
 82     for(int i=0;i<what.size();++i)
 83     {
 84         ll x=what[i];
 85         ans[x]+=wait[x];
 86         T[u].push(note(x,wait[x]));
 87         vis[x]=wait[x]=0;
 88     }
 89 }
 90 int get(int x)
 91 {
 92     int sum=0;
 93     for(int i=1;i*i<=x;++i)
 94         if(x%i==0)
 95             sum+=2;
 96     return sum;
 97 }
 98 int main()
 99 {
100     ios::sync_with_stdio(false);
101     cin>>n;
102     for(int i=1;i<=n;++i)
103         cin>>val[i];
104     for(int i=1;i<=n-1;++i)
105     {
106         int x,y;
107         cin>>x>>y;
108         add(x,y);
109         add(y,x);
110     }
111     dfs(1,1);
112     for(int i=1;i<=200000;++i)
113         if(ans[i])
114             cout<<i<<" "<<ans[i]<<endl;
115     return 0;
116 }

View Code