[文章目录]
Description
给你一个n个节点带有点权的树，要求你修改最少节点的权值，使得每个节点的权值等于其儿子节点权值的和，并且每个节点儿子的权值相同。n<=500000
正难则反，考虑一个节点权值不变，发现如果一个节点的权值固定，整棵树每个节点的权值就固定了。那么我们可以以一号节点的权值作为树区分的标记。对于每个点求出该点权值不变的时候一号节点的权值，最多相同权值个数即为保留的点的个数。
由于每个儿子权值转移到父亲时权值是指数增长的，发现所求出的一号节点的权值巨大。连乘关系？？？取个对数就好了，变成连加关系。
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
double a[500100],ans[500100],now;
vector<int>ed[500100];
void dfs(int x,int pre)
{
ans[x]=now+log(a[x]);
if(x!=1&&ed[x].size()>1) now+=log(ed[x].size()-1);
else if(x==1&&ed[x].size()) now+=log(ed[x].size());
for(int i=0;i!=(int)ed[x].size();++i) if(ed[x][i]!=pre)
dfs(ed[x][i],x);
if(x!=1&&ed[x].size()>1) now-=log(ed[x].size()-1);
else if(x==1&&ed[x].size()) now-=log(ed[x].size());
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lf",a+i);
int x,y;
for(int i=1;i!=n;++i)
{
scanf("%d%d",&x,&y);
ed[x].push_back(y); ed[y].push_back(x);
}
dfs(1,0); sort(ans+1,ans+n+1);
int fna=1,cnt=1;
for(int i=2;i<=n;++i)
{
if(fabs(ans[i]-ans[i-1])<1e-5) cnt++;
else fna=max(fna,cnt),cnt=1;
}
fna=max(fna,cnt);
printf("%d",n-fna);
return 0;
}