P3237 [HNOI2014]米特运输【题解】

题目描述

米特是 $D$ 星球上一种非常神秘的物质，蕴含着巨大的能量。在以米特为主要能源的 $D$ 星上，这种米特能源的运输和储存一直是一个大问题。

$D$ 星上有 $N$ 个城市，我们将其顺序编号为 $1$ 到 $N$ ， $1$ 号城市为首都。这 $N$ 个城市由 $N-1$ 条单向高速通道连接起来，构成一棵以 $1$ 号城市（首部）为根的树，高速通道的方向由树中的儿子指向父亲。树按深度分层：根结点深度为 $0$ ，属于第 $1$ 层；根结点的子节点深度为 $1$ ，属于第 $2$ 层；依此类推，深度为 $i$ 的结点属于第 $i+1$ 层。

建好高速通道之后， $D$ 星人开始考虑如何具体地储存和传输米特资源。由于发展程度不同，每个城市储存米特的能力不尽相同，其中第 $i$ 个城市建有一个容量为 $A[i]$ 的米特储存器。这个米特储存器除了具有储存的功能，还具有自动收集米特的能力。

如果到了晚上六点，有某个储存器处于未满的状态，它就会自动收集大气中蕴含的米特能源，在早上六点之前就能收集满；但是，只有在储存器完全空的状态下启动自动收集程序才是安全的，未满而又非空时启动可能有安全隐患。

早上六点到七点间，根节点城市（ $1$ 号城市）会将其储存器里的米特消耗殆尽。根节点不会自动搜集米特，它只接受子节点传输来的米特。

早上七点，城市之间启动米特传输过程，传输过程逐层递进：先是第 $2$ 层节点城市向第 $1$ 层（根节点城市，即 $1$ 号城市）传输，直到第 $1$ 层的储存器满或第2层的储存器全为空；然后是第 $3$ 层向第 $2$ 层传输，直到对于第 $2$ 层的每个节点，其储存器满或其予节点（位于第 $3$ 层）的储存器全为空；依此类推，直到最后一层传输完成。传输过程一定会在晚上六点前完成。

由于技术原因，运输方案需要满足以下条件：

不能让某个储存器到了晚上六点传输结束时还处于非空但又未满的状态，这个时候储存器仍然会启动自动收集米特的程序，而给已经储存有米特的储存器启动收集程序可能导致危险，也就是说要让储存器到了晚上六点时要么空要么满；

关于首都——即 $1$ 号城市的特殊情况，每天早上六点到七点间 $1$ 号城市中的米特储存器里的米特会自动被消耗殆尽，即运输方案不需要考虑首都的米特怎么运走；

除了 $1$ 号城市，每个节点必须在其子节点城市向它运输米特之前将这座城市的米特储存器中原本存有的米特全部运出去给父节点，不允许储存器中残存的米特与外来的米特发生混合；

运向某一个城市的若干个来源的米特数量必须完全相同，不然，这些来源不同的米特按不同比例混合之后可能发生危险。

现在 $D$ 星人已经建立好高速通道，每个城市也有了一定储存容量的米特储存器。为了满足上面的限制条件，可能需要重建一些城市中的米特储存器。你可以，也只能，将某一座城市（包括首都）中原来存在的米特储存器摧毁，再新建一座任意容量的新的米特储存器，其容量可以是小数（在输入数据中，储存器原始容量是正整数，但重建后可以是小数），不能是负数或零，使得需要被重建的米特储存器的数目尽量少。

输入输出格式

输入格式：

第一行是一个正整数 $N$ ，表示城市的数目。
接下来 $N$ 行，每行一个正整数，其中的第i行表示第i个城市原来存在的米特储存器的容量。
再接下来是 $N-1$ 行，每行两个正整数 $a$ ， $b$ 表示城市 $b$ 到城市 $a$ 有一条高速通道 $(a≠b)$ 。

输出格式：

输出文件仅包含一行，一个整数，表示最少的被重建（即修改储存器容量）的米特储存器的数目。

输入输出样例

输入样例#1：

5
5
4
3
2
1
1 2
1 3
2 4
2 5

输出样例#1：

3

说明

【样例解释】

一个最优解是将 $A[1]$ 改成 $8$ ， $A[3]$ 改成 $4$ ， $A[5]$ 改成 $2$ 。这样， $2$ 和 $3$ 运给 $1$ 的 $4$ 量相等， $4$ 和 $5$ 运给 $2$ 的量相等，且每天晚上六点的时候， $1$ ， $2$ 满， $3$ ， $4$ ， $5$ 空，满足所有限制条件。

对于 $100$ %的数据满足 $N<500000$ ， $A[j]<10^8$

题解：

题目太长，先转述一下题意吧
求使得父节点的权值为子节点的权值之和，且子节点权值相等的最少的修改次数

由样例解释可以发现，到晚上六点时叶子结点为空，其他节点满，而且每层的容量是相同的

那么我们有：对于树上任一个点，其权值一旦确定，整棵树的权值即可确定。

例如：

P3237 [HNOI2014]米特运输【题解】
从根往下递推，累计路径上的权值，如下图：

$图片来自Luogu BillYang$

!：不想写高精用 $log$ 将乘法转化为加法

$loga(MN)=logaM+logaN$

注意精度损失，要判EPS

代码：

#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<cmath>
#include<algorithm>
const double Eps=1e-8;
using namespace std;
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch))f|=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return f?-x:x;
}
int head[500007],cnt;
double a[500007];
int w[500007],out[500007];
struct Edge{int next,to;}edge[1000007];
inline void add_edge(int from,int to){
	edge[++cnt].next=head[from];
	edge[cnt].to=to;head[from]=cnt;
}
void dfs(int x,int fa,double sum){
	a[x]=sum+log(w[x]);
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa)continue;out[x]++;//统计当前节点的初度，也就是每层的节点数
	}
	for(int i=head[x];i;i=edge[i].next){
		int to=edge[i].to;
		if(to==fa)continue;
		dfs(to,x,sum+log(out[x]));
	}
}
int main(){
	int n=read(),lll=1,ans=1;
	for(int i=1;i<=n;++i)w[i]=read();
	for(int i=1;i<n;++i){
		int u=read(),v=read();
		add_edge(u,v);add_edge(v,u);
	}
	dfs(1,0,log(1));
	sort(a+1,a+n+1);
	for(int i=2;i<=n;++i)if(a[i]-a[i-1]<Eps)ans=max(ans,++lll);else lll=1;
	printf("%d",n-ans);
	return 0;
}