米特運輸——（dfs）
米特是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 【樣例解釋】 一個最優解是將A[1]改成8，A[3]改成4，A[5]改成2。 這樣，2和3運給1的量相等，4和5運給2的量相等，且每天晚上六點的時候，1，2滿，3，4，5空，滿足所有限
題解
Describe
啊，終於讀完了。
來給大家整理一下：
給一棵樹，每個點有一個權值，要求修改一些權值，使：
- 一個點的權值必須是其所有兒子的權值之和
- 一個點的兒子權值必須相同
求最少的被修改的數目
Solution
隨便畫一畫圖就可以找到一些顯著的規律,只要確定了一個點的權值就可以知道整顆樹的值了.
這裡就不詳細的給出圖進行解釋了,自己畫一畫圖就可以知道了.
於是我們可以令f[x]表示x這個點不變的話,根節點的值.
但是將子節點的個數成起來會爆long long,所以需要運用一點小技巧:log
運用公式:log(a∗b)=log(a)+log(b)。
答案就是n-(f[1]~f[n]數組中最多的相同個數).
Code
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=500000+5;
double f[maxn];
int v[maxn],head[maxn],s[maxn];
int n,x,y,maxx,js=1;
struct Edge{
int to,next;
}e[maxn];
void DFS(int son,int fa,double ans){
f[son]=ans+log(v[son]);
for(int i=head[son];i;i=e[i].next){
int v=e[i].to;
DFS(v,son,ans+log(s[son]));
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&v[i]);
for(int i=1;i<n;++i){
scanf("%d%d",&x,&y);
e[i].to=y;
e[i].next=head[x];
head[x]=i;
s[x]++;
}
DFS(1,0,log(1.0));
sort(f+1,f+1+n);
for(int i=2;i<=n;++i){
if(f[i]-f[i-1]<0.0001)js++;
else js=1;
maxx=max(maxx,js);
}
printf("%d\n",n-maxx);
return 0;
}
