TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3169
  • 题目
  • P3169水果姐逛水果街5
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    连续四天都没有被难倒,水果姐心情很不错,第四天又来逛水果街。

    今天root早早就来到了水果街等水果姐,因为他带来了帮手ZEALOT、xiaohao1、UncleGai还有nodgd。ZEALOT的魔法是把水果街变成有根树,xiaohao1的魔法是瞬间让某两家水果店之间的路径(包含端点)所有水果店的价格变成d。UncleGai的魔法是把以某家水果店为根的一颗子树的所有水果店的价格变成d,nodgd的魔法很厉害,他可以把任意一个节点变成根节点,他们一边改,root一边提问,绝不给水果姐思考的时间!

    同样还是n家水果店,编号为1~n,每家店能买水果也能卖水果,并且同一家店卖与买的价格一样。

    一共有m个操作。

    操作的格式为

    0 x y d
    1 x d
    2 x
    3 x y

    如果操作类型是0,表示xiaohao1把第x家店到第y家店的路径上所有的水果店的价格全部变成d

    如果操作类型是1,表示UncleGai把第x家店为根的子树上所有的水果店的价格全部变成d

    如果操作类型是2,表示nodgd把第x家店变成了根

    如果操作类型是3,则表示要求水果姐从第x家店出发到第y家店,途中只能选一家店买一个水果,然后选一家店(可以是同一家店,但不能往回走)卖出去。并且输出最多可以赚多少钱。

    输入格式

    第一行两个整数n,k,表示有n家店根为k

    下来n个正整数,表示每家店一个苹果的价格。

    下来n-1行,每行两个整数x,y,表示第x家店和第y家店有一条边。

    下来一个整数m,表示下来有m个操作。

    下来有m行,每行表示一次操作。

    输出格式

    每行对应一个2类型的操作,输出一个整数,表示面对root的每次询问,水果姐最多可以赚到多少钱。

    样例输入

    7 1
    1 2 3 4 5 6 7
    1 2
    2 3
    2 4
    1 5
    5 6
    6 7
    9
    3 7 1
    3 7 3
    0 4 5 8
    3 7 1
    1 2 10
    3 7 4
    2 6
    1 5 3
    3 3 7

    样例输出

    0
    2
    2
    4
    4

    提示

    0<=苹果的价格<=10^8

    1<=n<=200000

    1<=m<=100000


    来源  感谢ShadowIterator命题并提供数据