Pro.ID1643 TitleDFS 序 4 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1643 AC0 Submit0 Ratio- 时间&空间限制描述这是一道模板题。 本题严重卡常,请务必使用 fread 快读,不保证无快读的程序能过(虽然标程没用快读)。 给一棵有根树,这棵树由编号为 1…N 的 N 个节点组成。根节点的编号为 R 。每个节点都有一个权值,节点 i 的权值为 vi 。 接下来有 M 组操作,操作分为三类:
输入第一行有三个整数 N , M 和 R 。 第二行有 N 个整数,第 i 个整数表示 vi 。 在接下来的 N−1 行中,每行两个整数,表示一条边。 在接下来的 M 行中,每行一组操作。 40% 的数据不含操作 2。 1 ⩽ N , M ⩽ 106 , 1 ⩽ R ⩽ N , −106 ⩽ vi , x ⩽ 106 . 输出Description 这是一道模板题。 本题严重卡常,请务必使用 fread 快读,不保证无快读的程序能过(虽然标程没用快读)。 给一棵有根树,这棵树由编号为 1…N 的 N 个节点组成。根节点的编号为 R 。每个节点都有一个权值,节点 i 的权值为 vi 。 接下来有 M 组操作,操作分为三类:
Input 第一行有三个整数 N , M 和 R 。 第二行有 N 个整数,第 i 个整数表示 vi 。 在接下来的 N−1 行中,每行两个整数,表示一条边。 在接下来的 M 行中,每行一组操作。 40% 的数据不含操作 2。 1 ⩽ N , M ⩽ 106 , 1 ⩽ R ⩽ N , −106 ⩽ vi , x ⩽ 106 . Output 对于每组 3 a b 操作,输出一个整数,表示「节点 a 到节点 b 的简单路径」上所有节点的权值之和(含节点 a, b)。 Sample Input Sample #1 Sample Output Sample #1 Hint 标程可以过前4个测试文件,却不能过最后一个。 原因待考证。 样例输入Sample #1 样例输出Sample #1 提示标程可以过前4个测试文件,却不能过最后一个。 原因待考证。 作者 |