New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1805: [NewOJ Week 3] 黑白边

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：23 通过：15
提交提交记录统计

题目描述

给定个n个节点的树，编号为1-n，其中根节点编号为1。
对于所有其他节点i，到根节点的路径恰好只经过编号小于i的节点。
初始时所有边均为黑色。
现在给出两种操作：
  1. A x y：把<x,y>之间的边变成白色，其中<x,y>是原来树中的某一条边。
  2. W x：询问从1到x的路径上，黑色边的数量。

输入格式

第一行为正整数n。（1≤n≤250000)
接下来n-1行，每行两个整数u和v，表示存在从u到v的边。（1≤u, v≤n）
接下来1行包含一个m，表示询问次数。（1≤m≤250000)
接下来m+n-1行，表示累计m+n-1次操作，恰好包含m次询问操作，n-1次修改操作。
对于每次操作：首先输入一个字符op。
如果op等于‘A’，则输入两个数字x和y，表示<x,y>边变成白色，输入保证每条边最多改变1次。
如果op等于‘W’，则输入一个数字x，表示询问1到x的路径上，黑色边的数量。
输入输出数据较大，需要快速读入。

输出格式

对于每次询问，输出一行包含一个数字表示答案。

输入样例 复制 

5
1 2
1 3
1 4
4 5
4
W 5
A 1 4
W 5
A 4 5
W 5
W 2
A 1 2
A 1 3

输出样例 复制 

2
1
0
1