TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2252
  • 题目
  • P2252【USACO 2011 Dec Gold 】种草(弱数据版)
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    农夫约翰有N块贫瘠的牧场(2 <= N <= 100,000),有N-1条双向道路将这N个牧场连接了起来,每两个牧场间都有且仅有一条路径可相互到达。著名奶牛贝西经常抱怨:为什么连接牧场的道路上没有草可吃呢?

    约翰非常喜欢贝西,今天约翰终于决定要在道路上种草了。约翰的种草工作被分成了M(1 <= M <=100,000)步操作。
    在每一步中,下列两个事件中的一个会发生:
    1.约翰会选择两个牧场,沿着两个牧场间的路径,在路径上的每一条道路上都种植1株牧草;
    2.贝西会向约翰提问:在一条指定的道路上,种植了多少株牧草;

    请帮助约翰回答贝西的问题。

    输入格式

    第一行,两个空格间隔的整数N和M
    接下来N-1行,每行两个整数x和y,表示牧场x和y之间有道路直接相连
    接下来M行,每行描述一步操作:
    每行以字母P或Q作为开头,P代表种草操作,Q代表询问操作,接下来两个整数,A_i 和 B_i用于描述该步的操作(1 <= A_i, B_i <= N)。

    输出格式

    对于每一次询问,输出一行,一个整数,表示询问的答案

    样例输入 1

    4 6
    1 4
    2 4
    3 4
    P 2 3
    P 1 3
    Q 3 4
    P 1 4
    Q 2 4
    Q 1 4

    样例输出 1

    2
    1
    2

    样例输入 2

    6 6
    2 3
    3 4
    5 3
    6 1
    1 2
    Q 1 6
    P 6 4
    P 2 5
    Q 1 2
    P 6 5
    Q 2 3

    样例输出 2

    0
    1
    3

    提示

    数据较弱,递归程序可通过