TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3188
  • 题目
  • P3188小恶魔
    限制 : 时间限制 : 10000 MS   空间限制 : 262144 KB
    评测说明 : 2s,256MB
    问题描述

    从前有一个古老的王国,国王与恶魔相爱了。国王原本是很聪明的,而且深受国民的爱戴。但是现在,恶魔总是叫国王去做一些疯狂的事情。因为恶魔的外表是一个非常可爱的小萝莉,所以国王无法拒绝她的任何请求。
    该国的道路系统看起来就像是一棵树。每条路的颜色要么是黑色,要么是白色。恶魔喜欢制造混乱,她经常要求国王修改该国的道路。
    具体的说,如果一条边的两个端点都在点a到点b的路径上,我们称该边属于路径ab,如果一条边只有一个端点在路径ab上,我们称该边与路径ab相邻。
    有时候,恶魔会要求国王翻转路径上每条边的颜色,或者是翻转每条相邻边的颜色。有时候,恶魔会问国王在指定的一条路径上,有多少条黑色的边。请你帮助国王快速做出回答。
    一开始,每条边都是白色的。

    输入格式

    第一行,一个整数n,表示树中节点的个数,节点编号1到n。
    接下来n-1行,每行两个整数a,b,表示点a和点b间有边直接相连。
    接下来是一个整数m,表示恶魔的操作总数。
    接下来m行,每行表示一个操作,每行三个整数t,a,b。
    t==1表示翻转a到b路径上每条边的颜色;
    t==2表示翻转a到b路径上每条相邻边的颜色;
    t==3表示询问a到b路径上共有多少条黑色的边;
    0<=n,m<=100,000

    输出格式

    对于每次询问,输出一行,一个整数,表示所求结果。

    样例输入

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

    样例输出

    3

    提示

    说明:翻转一条边的颜色是指将其从白色改成黑色,或者从黑色改成白色。


    来源  来源:multi 2014 出题人:WJMZBMR 翻译:BossHe