P3237 [HNOI2014]米特运输

这个题目背景真的是太孙了，必须吐槽！

$Pro$

给一棵树，每个点有一个权值，要求修改一些权值，使：

一个点的权值必须是其所有儿子的权值之和
一个点的儿子权值必须相同

求最少的被修改的数目

$Sol$

其实此题充满套路的气息，首先，如果一个节点的权值确定，整个树都会确定。

假设节点 $u$ 的权值是 $val[u]$ ，孩子数量是 $son[u]$ ，假设确定是节点 $v$ ，对于节点 $v$ 的子节点 $w$ ， $val[w]=val[v]/son[v]$ ，对于节点 $v$ 的父节点 $f$ ， $val[f]=val[v] \times son[f]$ ，依次类推，可以知道所有权值。

考虑求出一个 $dp$ 数组，代表当前节点的权值不变的话，根节点的权值是多少，发现 $dp[u]=\prod _{v \in anc(u)} son[v] \times a[u]$ ，于是求出该数组里面出现次数最多的数，用 $n$ 减去即可，表示剩下的节点都要被修改。

注意到 $dp$ 数组会爆long long，于是考虑取 $\log$ 解决。

#include <bits/stdc++.h>
#define MAXN 500005
#define eps 1e-6
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int a[MAXN];
double dp[MAXN];
void dfs(int u,int father,double sum){
    dp[u]=log(a[u])+sum;
    double son=log(G[u].size()-(u==1?0:1));
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=father) dfs(v,u,sum+son);
    }
}
int main(){
    int n=read();
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    for (register int i=1;i<n;++i){
        int u=read(),v=read();
        AddEdge(u,v),AddEdge(v,u);
    }
    dfs(1,1,0);
    sort(dp+1,dp+1+n);
    int ans=1,cnt=0;
    for (register int i=1;i<n;++i){
        if (abs(dp[i]-dp[i+1])<=eps) ans=max(ans,++cnt);
        else cnt=1;
    }
    printf("%d\n",n-ans);
}