bzoj 3573:[Hnoi 2014]ミット輸送

転送ゲート:http://www.lydsy.com/JudgeOnline/problem.php?id=3573
考え方:国語の問題...
通常の問題:
1本のツリーと各ポイントの重み値を指定し、最低何ポイントの重み値を変更するかを尋ねます.
1.各点のすべての息子の権利値が等しい
2.各ポイントの重み付け値は、すべての子の重み付け値と等しい
この2つの条件がある以上、1つの点の重みを決定すると、木全体のすべての点の重みが決定されます.
各点が不変であることを列挙し,ルートノードの重み値を算出し,出現回数が最も多いスキームを選択すると,変更点数はn−スキーム数であり,このとき最小である.
ルートノードの重み値が大きいので、logまたはhashを取ればいいです.

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=500010,maxm=1000010;
const double eps=1e-7;
using namespace std;
int n,a[maxn],pre[maxm],now[maxn],son[maxm],cnt[maxn],fa[maxn],val[maxn],res,tot;double s[maxn],ans[maxn];
void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
void dfs1(int x){for (int y=now[x];y;y=pre[y]) if (fa[x]!=son[y]) cnt[x]++,fa[son[y]]=x,dfs1(son[y]);}
void dfs2(int x){
	for (int y=now[x];y;y=pre[y]) if (son[y]!=fa[x])
		s[son[y]]=s[x]+log(cnt[x]),dfs2(son[y]);
}

int main(){
	scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&val[i]);
	for (int i=1,a,b;i<n;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a);
	dfs1(1),s[1]=log(1.0),dfs2(1);
	for (int i=1;i<=n;i++) ans[i]=s[i]+log(val[i]);
	sort(ans+1,ans+1+n);
	int cnt=0;
	for (int i=1;i<=n;i++){
		if (fabs(ans[i]-ans[i-1])<eps) cnt++;
		else res=max(res,cnt),cnt=1;
	}
	res=max(res,cnt),printf("%d
",n-res);
	return 0;
}