P4242 树上的毒瘤

    • 18通过
    • 68提交
  • 题目提供者 Salamander
  • 评测方式 云端评测
  • 标签 分治 概率论,统计 虚树
  • 难度 普及+/提高
  • 时空限制 2000ms-3000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    Salamander开心地把一大袋毒瘤带回了家,把他们染上了不同的颜色,并把他们挂在了院子里的树上。

    题目描述

    这棵树上有 $n$ 个节点,由 $n-1$ 条树枝相连。初始时树上都挂了一个毒瘤,颜色为 $c_i$ 。接下来Salamander将会进行 $q$ 个操作。

    Salamander有时会修改树上某个点到另外一个点的简单路径上所有毒瘤的颜色。

    对于给定的树上某个点集 $S$ ,Salamander还定义了某个点的权值:

    $$W_i=\sum_{j\in S}T(i,j)$$

    其中 $T(i,j)$ 表示 $i$ 到 $j$ 的路径上毒瘤颜色的段数,比如 $i$ 到 $j$ 的路径上毒瘤颜色为 $1223312$ 时,颜色段数为 $5$ 。

    Salamander对树上的毒瘤们的状态很感兴趣,所以有时会指定树上 $m$ 个节点作为点集,询问这 $m$ 个节点的权值。

    输入输出格式

    输入格式:

    第一行包括两个正整数 $n$ 、 $q$ ,表示树上的节点数和操作个数。

    第二行包括用空格隔开的 $n$ 个正整数 $c_i$ ,表示树上每个节点初始的毒瘤颜色。

    接下来 $n-1$ 行,每行两个正整数 $u$ 、 $v$ ,表示树上有一条连接 $u$ 和 $v$ 的边。

    接下来描述 $q$ 个操作:

    • 1 若给出的第一个整数等于 $1$ ,那么接下来将会有三个正整数 $u$ 、 $v$ 、 $y$ ,表示将树上编号为 $u$ 的点到编号为 $v$ 的点的简单路径上的毒瘤颜色全都改为 $y$ 。

    • 2 若给出的第一个整数等于 $2$ ,那么接下来将会有一个正整数 $m$ ,表示指定的树上节点个数。下一行将会有 $m$ 个用空格隔开的互不相同的正整数,表示当前询问给定的 $m$ 个节点。

    输出格式:

    若干行,对于每个 $2$ 操作输出对应的答案。

    输入输出样例

    输入样例#1: 复制
    10 10
    708916891 100649777 100649777 544409200 100649777 47435517 47435517 708916891 644811607 544409200 
    3 2
    7 1
    8 1
    1 10
    3 4
    1 5
    9 2
    1 2
    3 6
    2 1
    6 
    2 6
    8 10 9 3 2 4 
    2 2
    7 8 
    2 1
    5 
    2 2
    6 10 
    2 3
    6 1 4 
    2 1
    7 
    1 9 8 100649777
    1 7 9 544409200
    2 4
    10 9 1 2 
    输出样例#1: 复制
    1 
    13 17 15 11 11 15 
    3 3 
    1 
    5 5 
    7 7 7 
    1 
    4 4 4 4 

    说明

    保证输入数据合法。

    对于30%的数据,有 $1\leq n,q\leq 1000$ , $\sum m\leq 5000$ 。

    对于60%的数据,有 $1\leq n,q\leq 20000$ , $\sum m\leq 100000$ 。

    对于100%的数据,有 $1\leq n,q\leq 100000$ , $c_i,y\leq 10^9$ , $\sum m\leq 200000$ , $m\leq n$ 。

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