「HNOI2014」米特运输 - 树形动规+对数 | Bill Yang's Blog

「HNOI2014」米特运输 - 树形动规+对数

题目大意:

给一棵树,每个点有一个权值,要求修改一些点的权值,使得:
①同一个父亲的儿子权值必须相同
②父亲的取值必须是所有儿子权值之和

题解:

对于树上任一个点,其权值一旦确定,整棵树的权值即可确定。
例如下图:

从根往下递推,累计路径上的权值,如下图:

将路径上权值的累乘积即为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;
}
本篇文章有用吗?有用还不快点击!
0%