TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2145
  • 問題
  • P2145【SDOI2011 第1轮 DAY1】染色
    制限 : 時間制限 : 40000 MS   メモリ制限 : 565536 KB
    問題説明

    给定一棵有个节点的无根树和m个操作,操作有2类:
    1、将节点a到节点b路径上所有点都染成颜色c;
    2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。
    请你写一个程序依次完成这m个操作。

    入力形式

    第一行包含2个整数n和m,分别表示节点数和操作数;
    第二行包含n个正整数表示n个节点的初始颜色
    下面n-1行每行包含两个整数x和y,表示x和y之间有一条无向边。
    下面m行每行描述一个操作:
    “C a b c”表示这是一个染色操作,把节点a到节点b路径上所有点(包括a和b)都染成颜色;
    “Q a b”表示这是一个询问操作,询问节点a到节点b(包括a和b)路径上的颜色段数量。

    出力形式

    对于每个询问操作,输出一行答案。

    サンプル入力

    6 5
    2 2 1 2 1 1
    1 2
    1 3
    2 4
    2 5
    2 6
    Q 3 5
    C 2 1 1
    Q 3 5
    C 5 1 2
    Q 3 5

    サンプル出力

    3
    1
    2

    ヒント

    【数据规模和约定】





    【友情提示】
      不允许使用编译开关改变栈空间大小,请选手尽量不要使用递归,以避免堆栈溢出。


    ソース  动态树