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

· · 题解

题目大意：

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

①同一个父亲的儿子权值必须相同

②父亲的取值必须是所有儿子权值之和

题解：

对于树上任一个点，其权值一旦确定，整棵树的权值即可确定。

例如下图：

从根往下递推，累计路径上的权值，如下图：

将路径上权值的累乘积即为f[i]，f[i]相同的表示他们同属于同一种合法方案（想一想，为什么？），最后sort一遍寻找相同最多的即可。

注意将所有权值累乘会爆long long，但使用高精度太麻烦，巧妙运用log转为加法。

代码如下：

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
    LL num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
vector<int>edges[500005];
LL n,cnt=1,ans=1;
double a[500005],f[500005];
void AddEdge(int x,int y) {
    edges[x].push_back(y);
}
void Dfs(int Now,double sum) {
    f[Now]=sum+log((double)a[Now]);
    for(int i=0; i<edges[Now].size(); i++) {
        int Next=edges[Now][i];
        Dfs(Next,sum+log((double)edges[Now].size()));
    }
}
int main() {
    n=Get_Int();
    for(int i=1; i<=n; i++)a[i]=Get_Int();
    for(int i=1; i<n; i++) {
        int x=Get_Int(),y=Get_Int();
        AddEdge(x,y);
    }
    Dfs(1,log(1.0));
    sort(f+1,f+n+1);
    for(int i=2; i<=n; i++)
        if(f[i]-f[i-1]<=1e-8) {
            cnt++;
            ans=max(ans,cnt);
        } else cnt=1;
    printf("%lld\n",n-ans);
    return 0;
}