[HNOI2014]米特运输
2024-10-18 10:31:07
显然知道一个节点就可以推出整棵树
然而直接乘会爆longlong
所以考虑取log
最后排序算众数即可
# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# include <math.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
return x * z;
}
const int MAXN(500010);
const double EPS(1e-8);
int n, cnt, ft[MAXN], a[MAXN], son[MAXN], ans;
double s[MAXN];
struct Edge{ int to, nt; } edge[MAXN << 1];
/*
s[i]表示i不变,根的a取对数后的值
对s排序,取最多的众数个数num
ans = n - num
*/
IL void Add(RG int u, RG int v){
edge[cnt] = (Edge){v, ft[u]}; ft[u] = cnt++; son[u]++;
}
IL void Dfs(RG int u){
for(RG int e = ft[u]; e != -1; e = edge[e].nt){
RG int v = edge[e].to;
s[v] = s[u] + log(son[u]);
Dfs(v);
}
s[u] += log(a[u]);
}
int main(RG int argc, RG char* argv[]){
n = Read();
for(RG int i = 1; i <= n; i++) a[i] = Read(), ft[i] = -1;
for(RG int i = 1, u, v; i < n; i++) u = Read(), v = Read(), Add(u, v);
Dfs(1);
sort(s + 1, s + n + 1);
for(RG int i = 2, num = 1; i <= n; i++)
if(s[i] - s[i - 1] < EPS) num++, ans = max(ans, num);
else num = 1;
printf("%d\n", n - ans);
return 0;
}
最新文章
- 【干货分享】流程DEMO-事务呈批表
- UICollectionView
- 3G数据请求
- 史航416第十次作业&;总结
- java-汉字转化拼音(纯java)
- C#编程总结 字符转码
- FreeSWITCH无法读取wav文件
- IOS设计模式-简单工厂
- iOS几种简单有效的数组排序方法
- Toast的替代者Snackbar
- linux根据该文件夹的读取权限和权限运行差异
- ajax jsonp跨域
- LanSoEditor_common ---android平台的视频编辑SDK
- CSS position 属性
- 收集一些工作中常用的经典SQL语句
- Facebook AI的工业级NLP开源框架—— Pytext
- 未来-区块链-IBM:IBM 区块链技术开发社区
- SpringBoot之get请求404
- 对象关系映射(ORM)框架GreenDao简介和基本使用
- linux 通过nvm安装node