简化题意:
一棵(n)个点的树,每一个点有个初始点权,第(i)个点点权为(A_i),要求任意节点的子节点权值相等,父节点权值等于子节点的和,问最少需要改变多少点的权值。
设节点(i)的子节点数量为(sz_i),点(i)修改以后的点权为(w_i)。
发现我们通过一个点(i)的权值可以得到所有相邻点的权值:它的每一个子节点就是(frac{w_i}{sz_i}),它的父节点(fa)的点权就是(w_i imes sz_{fa})。
于是我们假设我们确定了根节点的点权,那么我们就确定了每一个点的点权。对于任意点(i),设它的父亲到根的路径上的点为(p_1,p_2,p_3,...,p_m),那么该点的权值就是(frac{w_1}{Pi_{i=1}^mP_i}),即根节点的点权乘路径上所有点的子节点数量的乘积。
我们设一个点(i)的父节点到根节点的路径上所有点子节点数量的乘积为(k_i),并钦定(k_1=1)。
于是我们有(w_i=frac{w_1}{k_i})。
于是(w_1=w_i imes k_i)。
我们要求满足(w_i=A_i)的(i)数量最多。
已知如果点(i)满足条件,那么(w_1=k_i imes A_i)。
所以我们要找一个(w_1),使得上述条件满足的数量最多。
所以我们把每一个点(i)的(k_i imes A_i)存入哈希表,看一下表中数量最多的值的数量即可。
注意这个值是可以满足的最大数量,我们要输出的是需要修改的最小数量,所以要用(n)减这个最大值然后输出。
code:
哈希模数建议取3个以上比较保险。
#include<bits/stdc++.h>
using namespace std;
const int mod1=19260817;
const int mod2=998244353;
const int mod3=1e9+7;
struct edge{
int t,nxt;
}e[1000010];
struct hv{
int m1,m2,m3;
bool operator>(const hv&y)const{
return m1==y.m1?(m2==y.m2?m3>y.m3:m2>y.m2):m1>y.m1;
}
bool operator<(const hv&y)const{
return m1==y.m1?(m2==y.m2?m3<y.m3:m2<y.m2):m1<y.m1;
}
hv operator*(const int&y)const{
hv tmp;
tmp.m1=1ll*m1*y%mod1,tmp.m2=1ll*m2*y%mod2,tmp.m3=1ll*m3*y%mod3;
return tmp;
}
}k[500010];
int n,a[500010],u,v,cnt,be[500010],sz[500010],vis[500010],ans;
map<hv,int>mp;
void scan(int&x){
x=0;
char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
void add(int x,int y){
e[++cnt].t=y,e[cnt].nxt=be[x],be[x]=cnt;
}
void Getk(int x){
vis[x]=1;
hv upd=k[x]*sz[x];
for(int i=be[x];i;i=e[i].nxt)!vis[e[i].t]?k[e[i].t]=upd,Getk(e[i].t),0:0;
}
int main(){
scan(n);
for(int i=1;i<=n;++i)scan(a[i]);
for(int i=1;i<n;++i)scan(u),scan(v),add(u,v),add(v,u),++sz[u],++sz[v];
for(int i=2;i<=n;++i)--sz[i];
k[1]=(hv){1,1,1},Getk(1);
for(int i=1;i<=n;++i)ans=max(ans,++mp[k[i]*a[i]]);
printf("%d",n-ans);
return 0;
}