P3676 小清新数据结构题

    • 18通过
    • 144提交
  • 题目提供者fjzzq2002
  • 标签 树链剖分,树剖 概率论,统计 点分治 洛谷原创 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 2s / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目背景

    本题时限2s,内存限制256M

    题目描述

    在很久很久以前,有一棵n个点的树,每个点有一个点权。

    现在有q次操作,每次操作是修改一个点的点权或指定一个点,询问以这个点为根时每棵子树点权和的平方和。

    (题目不是很好懂,没看太懂的可以看看样例解释)

    输入输出格式

    输入格式:

    第一行两个整数n、q。

    接下来n-1行每行两个整数a和b,表示树中a与b之间有一条边,保证给出的边不会重复。

    接下来一行n个整数,第i个整数表示第i个点的点权。

    接下来q行每行两或三个数,如果第一个数为1,那么接下来有两个数x和y,表示将第x个点的点权修改为y,如果第一个数为2,那么接下来有一个数x,表示询问以x为根时每棵子树点权和的平方和。

    输出格式:

    对于每个询问输出答案。

    输入输出样例

    输入样例#1: 复制
    4 5
    1 2
    2 3
    2 4
    4 3 2 1
    2 2
    1 1 3
    2 3
    1 2 4
    2 4
    输出样例#1: 复制
    121
    140
    194

    说明

    样例解释

    这是一个菊花图,2与1、3、4间有边。

    一开始每个点点权分别为4、3、2、1。

    第一个询问以2为根,1、3、4子树中都只有本身一个点,2子树中有所有点,那么1、3、4子树中的点权和就分别是自己的点权4、2、1,2子树中的点权和就是4+3+2+1=10,$4^2+2^2+1^1+10^2=121$。

    接下来将第一个点点权修改为3,每个点点权分别为3、3、2、1。

    第二个询问以3为根,1、4子树中只有自己,2子树中有1、2、4,3子树中有所有点,1、4子树点权和就是自己的点权3、1,2子树点权和就是3+3+1=7,3子树点权和为3+3+2+1=9,$3^2+1^2+7^2+9^2=140$。

    接下来把第二个点点权修改为4,每个点点权分别为3、4、2、1。

    第三个询问以4为根,1、3子树点权和就是3和2,2子树点权和就是3+4+2=9,4子树点权和为3+4+2+1=10,$3^2+2^2+9^2+10^2=194$。

    数据范围

    对于10%的数据,$n,q \leq 2000$。

    对于40%的数据,$n,q \leq 60000$。

    对于另外30%的数据,保证每次询问的根都为1。

    对于100%的数据,$1 \leq n,q \leq 200000$,$-10 \leq$输入的每个点权$\leq 10$。

    建议使用输入优化,虽然标程没加读入优化也能过

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