题意

---

 

思考

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

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

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

最后注意空间。

---

 

代码

1 #include
      
         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
       
        T[maxn]; 33 vector
        
         t; 34 void dfs(int u,int F) 35 { 36     vector
         
          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
          
           >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<
           <<" "<
            
             <