Description：

此题重点在于读题，如果读懂了就发现要求的是问最少修改几个点的权值可以使得父节点的权值等于子节点权值和，各子节点权值相等。

$1\leqslant n \leqslant 500000$

Solution：

首先发现如果一个点权值确定了，那么整棵树权值都确定了，所以我们只要求出最多有多少个点在不修改这个点权值的情况下整棵树的权值相同，然后用 $n$ 减就是答案，可以把这个点的权值推到根节点上，用一个什么东西存下来，最后询问最多有多少个相同的，如果直接求的话根节点的值就是指数级的，化成 $\log$ 就可以避免这个问题，直接用 $\text{map}$ 判精度会炸，所以排序统计。

当然也可以取模哈希。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n;

#define MAXN 500010

int val[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int son[MAXN];

bool vis[MAXN];

double rate[MAXN];

void dfs(int k,double w)

{

	vis[k] = true;

	son[k] = 0;rate[k] = w;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		++son[k];

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dfs(e[i].to,rate[k] + log(son[k]));

	}

	return;

}

map<double,int> cnt;

int main()

{

	scanf("%d",&n);

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

	int a,b;

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

	{

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

		add(a,b);

	}

	dfs(1,0.0);

	for(int i = 1;i <= n;++i)rate[i] += log(val[i]);

	sort(rate + 1,rate + 1 + n);

	int cnt = 0,ans = 0x3f3f3f3f;

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

	{

		if(i == 1 || rate[i] - rate[i - 1] > 1e-8)cnt = 1;

		else

		{

			++cnt;

			ans = min(ans,n - cnt);

		}

	}

	cout << ans << endl;

	return 0;

}