#2220. 0417 t3
0417 t3
0417 t3
题目描述
预览输出 题目名称 集合 题目类型 传统型 输入 标准输入 输出 标准输出 每个测试点时限 4.0 秒 内存限制 1024 MiB 子任务数目 11 测试点是否等分 否 预览输出 集合(set) 集合(set) 【题目描述】 给定一棵n 个点的有根树T,树的节点从1 至n 标号,1 为根。每个点有两个整数 权值ai, bi。 称一个点集S 是好的当且仅当其满足以下条件: • ∀u, v ∈S 满足u 是v 的祖先,∃x̸ ∈S, y ∈S,使得 – x 在u 到v 的路径上; – by ≤bx。 给出q 组询问,每组询问给出正整数c, d,找到一个好的点集S 最大化c×(∑ u∈S au)+ d × (minu∈S bu)。你只需要给出这个最大值。当S 为空时,认为minu∈S bu = 0。 【输入格式】 从标准输入读入数据。 第一行两个整数n, q,描述树的节点数和询问次数。 接下来n −1 行,每行两个整数u, v,描述树的一条边。 接下来n 行,第i 行两个整数ai, bi,描述节点i 的权值。 接下来q 行,每行两个整数c, d,描述一组询问。 【输出格式】 输出到标准输出。 对于每组询问输出一行一个整数表示答案。 【样例1 输入】 3 4 1 1 2 2 1 3 3 1 ‐2 4 ‐2 1 5 ‐5 2 6 1 1 7 1 3 8 3 1 9 1 10 10 第2 页 共3 页 预览输出 集合(set) 【样例1 输出】 0 1 1 2 1 3 15 4 【样例1 解释】 四组询问选择的集合依次是∅, {2}, {1}, {3}。 【子任务】 对于所有测试数据, • 1 ≤n, q ≤3 × 105; • 1 ≤u̸ = v ≤n,保证给出的n −1 条边构成一棵树; • −104 ≤ai ≤104,−109 ≤bi ≤109; • 1 ≤c, d ≤108。 子任务编号 特殊性质 分值 n ≤ q ≤ 1 3 5 5 2 5 10 10 无 3 5 300 300 4 9 3000 3000 3 × 105 5 13 6 14 200 7 × 104 ∀1 ≤i ≤n −1,i 和i + 1 有一条边 7 7 3 × 105 3 × 105 8 6 9 15 200 7 × 104 无 10 13 3 × 105 3 × 105 11 10 第3 页 共3 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 4
1 2
1 3
1 -2
-2 1
-5 2
1 1
1 3
3 1
1 10
0
1
1
15