P3237 [HNOI2014] 米特运输

一、题意

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

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

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

求最少的被修改的数目

对于 \(100\%\) 的数据满足 N<500000，\(A_j<10^8\)

二、分析

观察发现只要树上任意一点的权值确定，那么整棵树的权值也就确定了

依次固定每一个节点的权值，求出相对应的根节点的权值

设 \(f[i]\) 表示固定第 \(i\) 个点的权值时根节点的权值

当固定 \(a[4]\) 时，\(f[1]=2 \times 2\times a[4]\)

当固定 \(a[7]\) 时，\(f[1]=2\times 1\times a[7]\)

当固定 \(a[3]\) 时，\(f[1]=2\times a[3]\)

设 \(k[i]\) 表示从根节点到 i 的路径上，所有父节点的子节点的数量的乘积

\[f[i]=a[i]\times k[i] \]

\(f[i]\) 呈指数级增长，累成会爆 \(long\;\;long\)，用 \(\log\) 缩小数据范围

\[\log (a\times b)= \log (a)+ \log (b) \]

ans 为 n-f 数组中出现的次数

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const double eps=1e-8;
int n,x,y,cnt,ans;
double a[N],f[N];
vector<int> e[N];
void dfs(int u,int fa,double sum){f[u]=sum+log(a[u]);for(auto i:e[u]){if(i==fa) continue;int l;if(fa==0) l=e[u].size();else l=e[u].size()-1;//当前节点的子节点数dfs(i,u,sum+log(l));}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];	for(int i=1;i<n;i++){cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}dfs(1,0,log(1.0));//log(1.0)=0sort(f+1,f+1+n);for(int i=2;i<=n;i++){if(f[i]-f[i-1]<=eps){cnt++;ans=max(ans,cnt);}else cnt=1;}cout<<n-ans<<'\n';return 0;
}