题目大意：
给一棵树，每个点有一个权值，要求修改一些点的权值，使得：
①同一个父亲的儿子权值必须相同
②父亲的取值必须是所有儿子权值之和
题解：
对于树上任一个点，其权值一旦确定，整棵树的权值即可确定。
例如下图：
从根往下递推，累计路径上的权值，如下图：
将路径上权值的累乘积即为f[i]，f[i]相同的表示他们同属于同一种合法方案（想一想，为什么？），最后sort一遍寻找相同最多的即可。
注意将所有权值累乘会爆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
50
51
52
53
54
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
vector<int>edges[500005];
LL n,cnt=1,ans=1;
double a[500005],f[500005];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs(int Now,double sum) {
f[Now]=sum+log((double)a[Now]);
for(int i=0; i<edges[Now].size(); i++) {
int Next=edges[Now][i];
Dfs(Next,sum+log((double)edges[Now].size()));
}
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
}
Dfs(1,log(1.0));
sort(f+1,f+n+1);
for(int i=2; i<=n; i++)
if(f[i]-f[i-1]<=1e-8) {
cnt++;
ans=max(ans,cnt);
} else cnt=1;
printf("%lld\n",n-ans);
return 0;
}
|
