$Describe$

谁出的题目啊?这么长的题面,看完就滚粗了.强烈谴责

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

1. 一个点的权值必须是其所有儿子的权值之和
2. 一个点的儿子权值必须相同
   求最少的被修改的数目

$Solution$

随便画一画图就可以找到一些显著的规律,只要确定了一个点的权值就可以知道整颗树的值了.

这里就不详细的给出图进行解释了,自己画一画图就可以知道了.

于是我们可以令$val[x]$表示$x$这个点不变的话,根节点的值.

但是将子节点的个数成起来会爆$long\ long$,所以需要运用一点小技巧:$log$

运用公式:$log(a*b)=log(a)*log(b)$

答案就是$n-val$数组中相同个数最多的.

$Code$

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
struct node {
    int to,next;
}a[500010<<1];
double val[500010];
int v[500010],head[500010],s[500010],cnt;
void add(int x,int y){
    a[++cnt].next=head[x],a[cnt].to=y,head[x]=cnt;
    a[++cnt].next=head[y],a[cnt].to=x,head[y]=cnt;
}
void dfs(int x,int fa,double ans){
    val[x]=ans+log(v[x]),s[x]--;
    for(int i=head[x];i;i=a[i].next){
    int v=a[i].to;
    if(v==fa)
        continue;
    dfs(v,x,ans+log(s[x]));
    }
}
main(){
    int n=read(),x,y,maxx=0,js=1;
    for(int i=1;i<=n;i++)
    v[i]=read();
    for(int i=1;i<n;i++)
    x=read(),y=read(),add(x,y),s[x]++,s[y]++;
    s[1]++,dfs(1,0,0);
    sort(val+1,val+1+n);
    for(int i=2;i<=n;i++){
    if(val[i]-val[i-1]<eps)
        js++;
    else maxx=max(maxx,js),js=1;
    }
    printf("%d",n-maxx);
}

E65 树形DP P3237 [HNOI2014] 米特运输

// 树形DP O(n)
#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N=500005,mod=1e9+7;
int n,a[N],s[N],ans;
vector<int> e[N];
map<int,int> mp;

void dfs(int u,int fa){
  if(u==1) s[u]=1;
  else if(fa==1) s[u]=e[fa].size();
  else s[u]=s[fa]*(e[fa].size()-1)%mod;
  for(int v:e[u]) 
    if(v!=fa) dfs(v,u);
}
signed main(){
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1,u,v;i<n;i++){
    cin>>u>>v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1,0);
  for(int i=1;i<=n;i++){
    ++mp[a[i]*s[i]%mod];
    ans=max(ans,mp[a[i]*s[i]%mod]);
  }
  cout<<n-ans;
}