题意：
给定一棵树上的边和点权
改动点权使得每个父节点u容量为子节点容量的d[u]（子节点个数）倍
考察点：
1.这是一道语文题
2.点权很大 直接算会爆 有一种优化办法：取log（醉 这是什么优化）
3.确定一个点的权值 整棵树的权值都可以确定
4.由3.可以得到一个脑洞很大的算法：算出每个点不变的情况下根节点的权值 然后算出这些根节点权值中一样的k个
n-k即是答案
这算个*的树形dp
这就是一道脑洞题
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define mod 1000000007 #define pa pair<int,int> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt; double a[500005],s[500005],val[500005]; int d[500005],last[500005]; struct edge{ int to,next; }e[1000005]; void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; e[++cnt]=(edge){u,last[v]};last[v]=cnt; } void dfs(int x,int fa) { for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { s[e[i].to]=s[x]+log(d[x]); dfs(e[i].to,x); } } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); d[u]++;d[v]++; } for(int i=2;i<=n;i++)d[i]--; s[1]=log(1); dfs(1,0); for(int i=1;i<=n;i++) val[i]=s[i]+log(a[i]); sort(val+1,val+n+1); int tmp=1,ans=0; for(int i=2;i<=n;i++) if(val[i]-val[i-1]<1e-5)tmp++; else ans=max(ans,tmp),tmp=1; ans=max(ans,tmp); printf("%d ",n-ans); return 0; }