RQNOJ系统遇到了一个程序错误。

您可以通过邮件support (at) rqnoj.cn与我们进行联系。请附错误参考编号:64412

美丽的中国结 - 题库 - RQNOJ
PID60 / 美丽的中国结
题目描述

题目背景

kitty刚刚高三毕业.看到同学们都回家的回家,旅游的旅游,她的心里有些落寞.英俊潇洒风流倜傥迷倒万千KL却仅对kitty感冒的fish看在眼里,急在心里.一天,fish提出和kitty两个人一起外出旅游.kitty犹豫了几天,想好能瞒过家长的理由后(要问是什么……自己猜去),答应了.fish很高兴地带着kitty去登记了(别想歪,登记旅游团而已……),日照青岛五日游.

当然啦,他们玩得很高兴.虽然这次旅行是fish先提议的,但kitty因为玩得很畅快(刚高考完嘛),所以想送给fish一份礼物,一份能让见多识广的fish都无法忘怀的礼物.她从路边 9¾站台的某算命先生那里得知中国结具有增加RP的效果,而这正是fish所需要的,因此她决定动手给fish编一个奇特的中国结.

题目描述

中国结形式多样,fish会喜欢什么样的呢?思考几天后,kitty决定给fish编一个树状的中国结.这个中国结有n个结点(编号1,2,…,n),这n个结点之间总共恰有n-1条线相连,其中结点1上是树的根.这是一个奇特的中国结,因此它的编织方式也很奇特.在编织过程中的每一步骤,kitty有时需要将一个结点子树里的所有结点i的状态全部取反(如果原来结点i已经打结,则解开i,否则将结点i打结),有时又需要知道一个结点的子树里有多少已经打结的结点,你能帮助可爱的kitty完成这份礼物吗?

数据规模

对于40% 的数据,1≤n≤10000, 1≤m≤20000

对于100%的数据,1≤n≤100000, 1≤m≤100000

输入格式

输入

第一行有个整数n,表示这个中国结有n个结点

以下n-1行,每行有两个整数u和v(1≤u,v≤n),表示结点u和v间有一条线相连;

再一行有个整数m,表示kitty要进行的步骤数

以下m行,每行可能为:

"C x":表示将结点x的子树中所有结点的状态取反(包括x)

"Q x":表示kitty想知道结点x的子树中有多少已经打结的结点(包括x)

输出格式

对于每个“Q x”输出一行整数,表示结点x的子树中有多少已经打结的结点(包括x)

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论