1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 50100010 #define llg long long11 #define md1 100000000712 #define md2 100000000913 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);14 llg n,m,du[maxn],ans,tail,val[maxn];15 vector<llg>a[maxn];16 struct node17 {18     llg v1,v2;19 }dl[maxn];20 21 bool cmp(const node a,const node&b) {if (a.v1==b.v1) return a.v2<b.v2;else return a.v1<b.v1;}22 23 void init()24 {25     cin>>n;26     for (llg i=1;i<=n;i++) scanf("%lld",&val[i]);27     for (llg i=1;i<n;i++)28     {29         llg x,y;30         scanf("%lld%lld",&x,&y);31         a[x].push_back(y); du[x]++;32     }33 }34 35 void dfs(llg x,llg fa,llg v1,llg v2)36 {37     llg w=a[x].size();38     dl[++tail].v1=(v1*val[x])%md1;39     dl[tail].v2=(v2*val[x])%md2;40     v1*=du[x],v2*=du[x];41     v1%=md1,v2%=md2;42     for (llg i=0;i<w;i++) 43     {44         dfs(a[x][i],x,v1,v2);45     }46 }47 48 int main()49 {50     yyj("a");51     init();52     dfs(1,0,1,1);53     sort(dl+1,dl+tail+1,cmp);54     ans=n;55     for (llg l=1;l<=tail;l++)56     {57         llg r=l;58         while (r+1<=tail)59         {60             if (dl[l].v1!=dl[r+1].v1 || dl[l].v2!=dl[r+1].v2) break;61             r++;62         }63         ans=min(ans,n-(r-l+1));64     }65     cout<<ans;66     return 0;67 }