P3237 [HNOI2014]米特运输

显然，对于一个点确定了，那么整棵树都确定了，因此我们枚举每个点作为不变点

之后用f[i]表示该节点固定时答案是多少，这样就能跑出正确答案了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e7+7;
const double eps=1e-6;
int h[N],ne[N],e[N],idx;
int w[N];
double f[N];
int in[N];
int a[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
ll dfs(int u,int fa,double ans){
    f[u]=ans+log(a[u]);
    in[u]--;
    int i;
    for(i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa)
            continue;
        dfs(j,u,ans+log(in[u]));
    }
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int i;
    memset(h,-1,sizeof h);
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    for(i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
        in[x]++,in[y]++;
    }
    in[1]++;
    dfs(1,-1,0);
    sort(f+1,f+1+n);
    int mx=0;
    int cnt=1;
    for(i=2;i<=n;i++){
        if(f[i]-f[i-1]<eps){
            cnt++;
        }
        else{
            mx=max(mx,cnt);
            cnt=1;
        }
    }
    cout<<n-mx<<endl;
}