题目传送门(BZOJ)
>原文链接<

题解 :

其实题目核心思想不太难,但是题难理解。

简化一下,其实就是改变一些点权,使得每个节点的所有儿子权值相同,且加和等于自己的权值。

有这样一个性质 :若一个点权,那么整棵树都确定了。

  • 一个点$p$的$val$确定了,它父亲的权值就是$val_p\times son[fa]$ 其中$son$代表儿子个数。

  • 同理,它的儿子们的$val$也确定了,就是$val_p/son[p]$。进而可以确定整棵树。

那么我们从根节点开始预处理,每个点的点权和根的倍数关系是确定的,先把它们和根的倍数关系处理出来。

设这个倍数是$s[i]$,我们的任务就是找到一个合适的根节点点权,使得在满足这个倍数关系的条件下,原始点权尽可能多的等于现在根节点点权的对应倍数。

但是我们发现这个不能枚举,太慢了,需要转思路。

改成求在当前点权下,乘以对应倍数得出根的权值的众数,这样,答案就是$N-$众数。

这个倍数是一个不到$1$的小数,我们可以把它取倒,结果是一样的,但这样还是爆$long long$

需要用数学方法优化一下 :$\log x \times \log y = \log (x+y)$

把它们都取个 $\log$ ,相当于可以做乘法的哈希,这样再取众数就可以了 。(貌似哈希也可以直接做)。

注意精度问题。

代码 :

#include <cmath>#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define f2 double#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000], *p1, *p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}const int N = 510000;struct Edge { int to; Edge *next;}*h[N], e[N<<1];int d[N], n, a[N];const f2 eps = 1e-6;f2 s[N];inline void Add_Edge(int u, int v) { static int _; d[u] ++ ; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}void dfs(int p, int fa) { rev(i, p) if(i->to != fa) { s[i->to] = s[p] + log(d[p]); dfs(i->to, p); } s[p] += log(a[p]);}int main() { n = rd(); for(int i = 1; i <= n; i ++ ) a[i] = rd(); for(int i = 2; i <= n; i ++ ) { int u = rd(), v = rd(); Add_Edge(u, v), Add_Edge(v, u); d[i] -- ; } s[1] = log(1); dfs(1, 0); sort(s+1, s+n+1); int tmp = 0, ans = 0; for(int i = 2; i <= n; i ++ ) { if(s[i]-s[i-1]<eps) tmp ++; else ans = max(ans, tmp), tmp = 1; } printf("%d\n", n-max(ans, tmp));}