Description:

給你一棵樹,每個點有權(quán)值,你可以修改一些點的權(quán)值使得:
1.每個點權(quán)值等于子節(jié)點權(quán)值的和
2.每個點的所有子節(jié)點權(quán)值相等

Hint:

\(n \le 2*10^6\)

Solution:

比較巧妙的題

首先有一個很顯然的規(guī)律:

當(dāng)一個點權(quán)值確定,整棵樹就確定了 (為什么這么顯然的規(guī)律沒有想到)

然后我們考慮轉(zhuǎn)化求對于每個點不改它,對應(yīng)的樹的形態(tài)

我們找出哪種樹的形態(tài)\(i\)被計的最多,答案就是\(n-cnt_i\)

于是\(f[i]=a[i]*\prod_{j\in {anc_i} } son[j]\)

dfs之后sort一遍就行

但是這樣會炸,要把乘換成加法\(-> log(x*y)=log(x)+log(y)\)

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=2e6+5;
const double eps=1e-8;
int n,m,cnt,ans,a[mxn],son[mxn],hd[mxn];
double f[mxn];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(int &x,int y) {if(x<y) x=y;}
inline void chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {
    int to,nxt;
}t[mxn<<1];

inline void add(int u,int v) {
    t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}

void dfs(int u,double sum) {
    f[u]=sum+log(a[u]);
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        dfs(v,sum+log(son[u]));
    }
}

int main()
{
    n=read(); int u,v;
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<n;++i) {
        u=read(); v=read();
        ++son[u]; add(u,v);
    }
    dfs(1,0); sort(f+1,f+n+1); int mx=1;
    for(int i=2;i<=n;++i) {
        if(f[i]-f[i-1]<=eps) ans=max(ans,++mx);
        else mx=1;
    }
    printf("%d\n",n-ans);
    return 0;
}