題目連結：傳送門 冗長冗長的題面：
Description
米特是D星球上一種非常神秘的物質，蘊含着巨大的能量。在以米特為主要能源的D星上，這種米特能源的運輸和儲存一直是一個大問題。D星上有N個城市，我們将其順序編号為1到N，1号城市為首都。這N個城市由N-1條單向高速通道連接配接起來，構成一棵以1号城市（首部）為根的樹，高速通道的方向由樹中的兒子指向父親。樹按深度分層：根結點深度為0，屬于第1層；根結點的子節點深度為1，屬于第2層；依此類推，深度為i的結點屬于第i+l層。建好高速通道之後，D星人開始考慮如何具體地儲存和傳輸米特資源。由于發展程度不同，每個城市儲存米特的能力不盡相同，其中第i個城市建有一個容量為A[i]的米特儲存器。這個米特儲存器除了具有儲存的功能，還具有自動收集米特的能力。如果到了晚上六點，有某個儲存器處于未滿的狀态，它就會自動收集大氣中蘊含的米特能源，在早上六點之前就能收集滿；但是，隻有在儲存器完全空的狀态下啟動自動收集程式才是安全的，未滿而又非空時啟動可能有安全隐患。早上六點到七點間，根節點城市（1号城市）會将其儲存器裡的米特消耗殆盡。根節點不會自動搜集米特，它隻接受子節點傳輸來的米特。早上七點，城市之間啟動米特傳輸過程，傳輸過程逐層遞進：先是第2層節點城市向第1層（根節點城市，即1号城市）傳輸，直到第1層的儲存器滿或第2層的儲存器全為空；然後是第3層向第2層傳輸，直到對于第2層的每個節點，其儲存器滿或其予節點（位于第3層）的儲存器全為空；依此類推，直到最後一層傳輸完成。傳輸過程一定會在晚上六點前完成。
由于技術原因，運輸方案需要滿足以下條件：
(1)不能讓某個儲存器到了晚上六點傳輸結束時還處于非空但又未滿的狀态，這個時候儲存器仍然會啟動自動收集米特的程式，而給已經儲存有米特的儲存器啟動收集程式可能導緻危險，也就是說要讓儲存器到了晚上六點時要麼空要麼滿；
(2)關于首都——即1号城市的特殊情況， 每天早上六點到七點間1号城市中的米特儲存器裡的米特會自動被消耗殆盡，即運輸方案不需要考慮首都的米特怎麼運走；
(3)除了1号城市，每個節點必須在其子節點城市向它運輸米特之前将這座城市的米特儲存器中原本存有的米特全部運出去給父節點，不允許儲存器中殘存的米特與外來的米特發生混合；
(4)運向某一個城市的若幹個來源的米特數量必須完全相同，不然，這些來源不同的米特按不同比例混合之後可能發生危險。
現在D星人已經建立好高速通道，每個城市也有了一定儲存容量的米特儲存器。為了滿足上面的限制條件，可能需要重建一些城市中的米特儲存器。你可以，也隻能，将某一座城市（包括首都）中原來存在的米特儲存器摧毀，再
建立一座任意容量的新的米特儲存器，其容量可以是小數（在輸入資料中，儲存器原始容量是正整數，但重建後可以是小數），不能是負數或零，使得需要被重建的米特儲存器的數目盡量少。
Input
第一行是一個正整數N，表示城市的數目。
接下來N行，每行一個正整數，其中的第i行表示第i個城市原來存在的米特儲存器的容量。
再接下來是N-I行，每行兩個正整數a，b表示城市b到城市a有一條高速通道(a≠b)。
N<500000，A[j]<10^8
Output
輸出檔案僅包含一行，一個整數，表示最少的被重建（即修改儲存器容量）的米特儲存器的數目。
Sample Input
5
5
4
3
2
1
1 2
1 3
2 4
2 5
Sample Output
3
【樣例解釋】
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <vector>
#include <iomanip>
#define
#define
#define
using namespace std;
struct node {
int next, to;
}edge[A];
int head[A], num_edge;
double cnt[A];
void add_edge(int from, int to) {
edge[++num_edge].next = head[from];
edge[num_edge].to = to;
head[from] = num_edge;
}
double w[A], f[A];
int n, a, b;
void dfs(int fr, double st, int fa) {
f[fr] = st + log(w[fr]);
for (int i = head[fr]; i; i = edge[i].next) {
int ca = edge[i].to;
if (ca == fa) continue;
dfs(ca, st + log(cnt[fr]), fr);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i < n; i++) {
cin >> a >> b;
add_edge(a, b);
add_edge(b, a);
cnt[a]++;
}
dfs(1, log(1.0), 1);
sort(f + 1, f + n + 1);
int tot = 1, ans = 1;
for (int i = 2; i <= n; i++)
if (f[i] - f[i - 1] <= 1e-8)
tot++, ans = max(ans, tot);
else tot = 1;
cout << n - ans << endl;
}