Steven_MengのBlog

传送门

这个题目背景真的是太孙了,必须吐槽!

$Pro$

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

  1. 一个点的权值必须是其所有儿子的权值之和
  2. 一个点的儿子权值必须相同

求最少的被修改的数目

$Sol$

其实此题充满套路的气息,首先,如果一个节点的权值确定,整个树都会确定。

假设节点$u$的权值是$val[u]$,孩子数量是$son[u]$,假设确定是节点$v$,对于节点$v$的子节点$w$,$val[w]=val[v]/son[v]$,对于节点$v$的父节点$f$,$val[f]=val[v] \times son[f]$,依次类推,可以知道所有权值。

考虑求出一个$dp$数组,代表当前节点的权值不变的话,根节点的权值是多少,发现$dp[u]=\prod _{v \in anc(u)} son[v] \times a[u]$,于是求出该数组里面出现次数最多的数,用$n$减去即可,表示剩下的节点都要被修改。

注意到$dp$数组会爆long long,于是考虑取$\log$解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define MAXN 500005
#define eps 1e-6
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<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
G[u].push_back(v);
}
int a[MAXN];
double dp[MAXN];
void dfs(int u,int father,double sum){
dp[u]=log(a[u])+sum;
double son=log(G[u].size()-(u==1?0:1));
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v!=father) dfs(v,u,sum+son);
}
}
int main(){
int n=read();
for (register int i=1;i<=n;++i){
a[i]=read();
}
for (register int i=1;i<n;++i){
int u=read(),v=read();
AddEdge(u,v),AddEdge(v,u);
}
dfs(1,1,0);
sort(dp+1,dp+1+n);
int ans=1,cnt=0;
for (register int i=1;i<n;++i){
if (abs(dp[i]-dp[i+1])<=eps) ans=max(ans,++cnt);
else cnt=1;
}
printf("%d\n",n-ans);
}

 评论