bzoj 3573: [Hnoi2014]米特运输【树形dp+瞎搞】

阅读理解题，题意是以1为根的有根树，每个点有点权，求修改最少点权能使每个点的权值等于其所有子节点权值之和并且每个点的所有子节点权值相等的个数

然后就比较简单了，就是有个技巧是数太大，需要对所有操作都取log

因为一个点的权值可以确定整棵树，所以求出每个点权值不变的总权值，看看最多有几个相等，记为mx，答案就是n-mx

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=500005;
int n,h[N],cnt,d[N];
double a[N],s[N],v[N];
struct qwe
{
int ne,to;
}e[N<<1];
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
void add(int u,int v)
{
cnt++;
e[cnt].ne=h[u];
e[cnt].to=v;
h[u]=cnt;
}
void dfs(int u,int fa)
{
for(int i=h[u];i;i=e[i].ne)
if(e[i].to!=fa)
{
s[e[i].to]=s[u]+log(d[u]);
dfs(e[i].to,u);
}
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y),add(y,x);
d[x]++,d[y]++;
}
for(int i=2;i<=n;i++)
d[i]--;
s[1]=log(1);
dfs(1,0);
for(int i=1;i<=n;i++)
v[i]=s[i]+log(a[i]);
sort(v+1,v+1+n);
int ans=0,len=1;
for(int i=2;i<=n;i++)
{
if(v[i]-v[i-1]<=1e-6)
len++;
else
ans=max(ans,len),len=1;
}
ans=max(ans,len);
printf("%d\n",n-ans);
return 0;
}