#PQJ2758x15144. QOJ 2758_15144
QOJ 2758_15144
T1(T1.in | T1.out | T1.cpp) 时间限制:1S 空间限制:256MB 【题目描述】 有一棵点数为N 的树,树边有边权。给你一个在0~N 之内的正整 数K,你要在这棵树中选择K 个点,将其染成黑色,并将其他的 N-K 个点染成白色。将所有点染色后,你会获得黑点两两之间的距 离加上白点两两之间的距离的和的受益。问受益最大值是多少。 【输入格式】 输入文件为T1.in。 文件第一行包含两个整数N, K。 接下来N-1 行每行三个正整数fr, to, dis,表示该树中存在一条长度 为dis 的边(fr, to)。输入保证所有点之间是联通的。 【输出格式】 输出文件为T1.out。 输出一个正整数,表示收益的最大值。 【输入样例1】 3 1 1 2 1 1 3 2 【输出样例1】 3 【输入样例2】 5 2 1 2 3 1 5 1 2 3 1
2 4 2 【输出样例2】 17 【样例解释】 在第二个样例中,将点1,2 染黑就能获得最大收益。 【数据范围】 对于30%的数据,N<=20; 对于50%的数据,N<=100; 对于100%的数据,0<=K<=N。 T2(T2.in | T2.out | T2.cpp) 时间限制:1S 空间限制:256MB 【题目描述】 有一棵点数为N 的树,以点1 为根,且树点有边权。然后有M 个 操作,分为三种: 操作1:把某个节点x 的点权增加a。 操作2:把某个节点x 为根的子树中所有点的点权都增加a。 操作3:询问某个节点x 到根的路径中所有点的点权和。 【输入格式】 输入文件为T2.in。 文件第一行包含两个整数N, M。表示点数和操作数。 接下来一行N 个整数,表示树中节点的初始权值。 接下来N-1 行每行三个正整数fr, to,表示该树中存在一条边(fr, to)。