扭动的树
Description
有一棵以key为键值以val为权值的二叉查找树（左子树的key值都比根节点key值小，右子树的key值都比根节点的key值大），定义其某个节点的sum为它的子树内节点的val值之和。给出n个<key, val>正整数对，现需保证这棵树上任意一条边的两个端点的key值的最大公约数不为1，询问这棵树上所有节点的sum之和最大可能是多少。如果这棵树不存在任意一个合法形态，输出-1。
Input
第一行为一个整数n。
接下来n行每行两个正整数key[i], val[i]。
Output
输出仅一行一个整数表示答案。
Sample Input
6
8 1
8 1
9 4
4 5
6 1
4 4
Sample Output
45
Hint
对于1号测试点（5%）：key[i]=1。
对于1~3号测试点（15%）：1≤n≤10。
对于1~10号测试点（50%）：1≤n≤50。
对于4~14号测试点（55%）：key[i]互不相同。
对于15~16号测试点（10%）：所有key[i]都相同。
对于所有测试点（100%）：1≤n≤300,1≤key[i]≤10^18,1≤val[i]≤10^6。
Source
2018NOIP国庆集训
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复