P3178 [HAOI2015]树上操作

    • 1.2K通过
    • 4.1K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 树链剖分,树剖 深度优先搜索,DFS 线段树 2015 河南 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:操作 1 :把某个节点 x 的点权增加 a 。操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 :询问某个节点 x 到根的路径中所有点的点权和。

    输入输出格式

    输入格式:

    第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数,表示树中节点的初始权值。接下来 N-1 行每行两个正整数 from, to , 表示该树中存在一条边 (from, to) 。再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。

    输出格式:

    对于每个询问操作,输出该询问的答案。答案之间用换行隔开。

    输入输出样例

    输入样例#1: 复制
    5 5
    1 2 3 4 5
    1 2
    1 4
    2 3
    2 5
    3 3
    1 2 1
    3 5
    2 1 2
    3 3
    输出样例#1: 复制
    6
    9
    13

    说明

    对于 100% 的数据, N,M<=100000 ,且所有输入数据的绝对值都不

    会超过 10^6 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。