HNOI2014 米特运输

P3237 [HNOI2014] 米特运输

题目大意

有一棵有$n$个节点的树，每个点有一个权值，要求修改一些点的权值，使得：

• 同一个父亲节点的所有儿子节点的权值相同
• 父亲节点的权值必须是所有儿子结点的权值之和

求需要修改的最小次数。

$1\le n\le 5\times 10^5$

题解

我们发现，当树上一个点的权值确定之后，树上所有的点的权值都可以确定。那么，对于每个点$i$，我们可以求出当这个点的权值不修改时，根节点的权值$c_i$。

对于两个点$i$和$j$，如果$c_i==c_j$，则当根节点的权值取$c_i$时，这两个点的权值都不需要修改。那么我们只需要给$c$值排序，再求出最多有多少个$c_i$的值相同。若最多有$k$个$c_i$的值相同，则答案为$n?k$。

不过，我们发现$c_i$的值可能很大，而求$c_i$是点$i$原来的权值乘上从点$i$的父亲到根节点的每个点的儿子个数之积，所以我们可以用$log$将乘法转化为加法，那么就不会出现$c_i$存不下的情况。

时间复杂度为$O(n\log n)$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=500000;
const double eps=1e-8;
int n,tot=0,d[2*N+5],l[2*N+5],r[N+5],a[N+5],ct[N+5];
int now=0,ans=0;
double b[N+5];
void add(int xx,int yy){
	l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs(int u,int fa,double sum){
	b[u]+=sum;
	sum+=log(ct[u]-(u>1));
	for(int i=r[u];i;i=l[i]){
		if(d[i]==fa) continue;
		dfs(d[i],u,sum);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=log(a[i]);
	}
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
		++ct[x];++ct[y];
	}
	dfs(1,0,0);
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
		if(i>1&&fabs(b[i]-b[i-1])>eps){
			ans=max(ans,now);
			now=0;
		}
		++now;
	}
	ans=max(ans,now);
	ans=n-ans;
	printf("%d",ans);
	return 0;
}