扭动的树
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 人评分
简单的a+b (C语言代码)浏览:671 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:664 |
字符串的输入输出处理 (C语言代码)浏览:926 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:520 |
C语言训练-尼科彻斯定理 (C语言代码)浏览:466 |
简单的a+b (C语言代码)浏览:629 |
WU-C语言程序设计教程(第三版)课后习题12.1 (C++代码)浏览:931 |
C语言考试练习题_一元二次方程 (C语言代码)浏览:576 |
母牛的故事 (C语言代码)浏览:549 |
简单的a+b (C语言代码)浏览:537 |
lalalala 2018-11-01 21:45:29 |
木有!!
lalalala 2018-11-01 21:50:42 |
这题应该是变异版的最大子树和。
HzuWHF 2018-11-01 21:51:55 |
@zhangshuo 我不会, 蛮好奇的, 做出了记得教我qaq
lalalala 2018-11-01 21:53:03 |
我顶多只能写一个暴搜将这个树遍历一遍。