TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2843
  • 题目
  • P2843【SDOI2014 R1D1】旅行
    限制 : 时间限制 : 40000 MS   空间限制 : 565536 KB
    问题描述

    S国有N个城市,编号从1到N。城市间用N-1条双向道路连接,满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教,如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便,我们用不同的正整数代表各种宗教。
    S国的居民常常旅行。旅行时他们总会走最短路,并且为了避免麻烦,只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级,旅行者们常会记下途中(包括起点和终点)留宿过的城市的评级总和或最大值。
    在S国的历史上常会发生以下几种事件:
    • "CC x c":城市x的居民全体改信了c教;
    • "CW x w":城市x的评级调整为w;
    • "QS x y":一位旅行者从城市x出发,到城市y,并记下了途中留宿过的城市的评级总和;
    • "QM x y":一位旅行者从城市x出发,到城市y,并记下了途中留宿过的城市的评级最大值。
    由于年代久远,旅行者记下的数字已经遗失了,但记录开始之前每座城市的信仰与评级,还有事件记录本身是完好的。请根据这些信息,还原旅行者记下的数字。
    为了方便,我们认为事件之间的间隔足够长,以致在任意一次旅行中,所有城市的评级和信仰保持不变。

    输入格式

    输入的第一行包含整数N,Q,依次表示城市数和事件数。
    接下来N行,第i+1行两个整数Wi,Ci依次表示记录开始之前,城市i的评级和信仰。
    接下来N-1行每行两个整数x,y表示一条双向道路。
    接下来Q行,每行一个操作,格式如上所述。

    输出格式

    对每个QS和QM事件,输出一行,表示旅行者记下的数字。

    样例输入

    5 6 
    3 1 
    2 3 
    1 2 
    3 3 
    5 1 
    1 2 
    1 3 
    3 4 
    3 5 
    QS 1 5 
    CC 3 1 
    QS 1 5 
    CW 3 3 
    QS 1 5 
    QM 2 4

    样例输出

    8
    9
    11
    3

    提示

    来源  感谢nodgd放题