{"problem":{"name":"E. Danil and a Part-time Job","description":{"content":"Danil decided to earn some money, so he had found a part-time job. The interview have went well, so now he is a light switcher. Danil works in a rooted tree (undirected connected acyclic graph) with ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF877E"},"statements":[{"statement_type":"Markdown","content":"Danil decided to earn some money, so he had found a part-time job. The interview have went well, so now he is a light switcher.\n\nDanil works in a rooted tree (undirected connected acyclic graph) with _n_ vertices, vertex 1 is the root of the tree. There is a room in each vertex, light can be switched on or off in each room. Danil's duties include switching light in all rooms of the subtree of the vertex. It means that if light is switched on in some room of the subtree, he should switch it off. Otherwise, he should switch it on.\n\nUnfortunately (or fortunately), Danil is very lazy. He knows that his boss is not going to personally check the work. Instead, he will send Danil tasks using _Workforces_ personal messages.\n\nThere are two types of tasks:\n\n1.  _pow v_ describes a task to switch lights in the subtree of vertex _v_.\n2.  _get v_ describes a task to count the number of rooms in the subtree of _v_, in which the light is turned on. Danil should send the answer to his boss using _Workforces_ messages.\n\nA subtree of vertex _v_ is a set of vertices for which the shortest path from them to the root passes through _v_. In particular, the vertex _v_ is in the subtree of _v_.\n\nDanil is not going to perform his duties. He asks you to write a program, which answers the boss instead of him.\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 200 000) — the number of vertices in the tree.\n\nThe second line contains _n_ - 1 space-separated integers _p_2, _p_3, ..., _p__n_ (1 ≤ _p__i_ < _i_), where _p__i_ is the ancestor of vertex _i_.\n\nThe third line contains _n_ space-separated integers _t_1, _t_2, ..., _t__n_ (0 ≤ _t__i_ ≤ 1), where _t__i_ is 1, if the light is turned on in vertex _i_ and 0 otherwise.\n\nThe fourth line contains a single integer _q_ (1 ≤ _q_ ≤ 200 000) — the number of tasks.\n\nThe next _q_ lines are _get v_ or _pow v_ (1 ≤ _v_ ≤ _n_) — the tasks described above.\n\n## Output\n\nFor each task _get v_ print the number of rooms in the subtree of _v_, in which the light is turned on.\n\n[samples]\n\n## Note\n\n<center>![image](https://espresso.codeforces.com/d6781a445b05890d8f89b31e73e0a5e630aefabb.png) The tree before the task _pow 1_.![image](https://espresso.codeforces.com/b7c3bb7bfafacc24c8a8074f560c2b58f380b399.png) The tree after the task _pow 1_.\n\n</center>","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Danil 决定赚些钱，于是找到了一份兼职工作。面试进行得很顺利，现在他是一名灯光开关员。\n\nDanil 在一棵有 #cf_span[n] 个顶点的有根树（无向连通无环图）中工作，顶点 #cf_span[1] 是树的根。每个顶点都有一个房间，每个房间的灯可以打开或关闭。Danil 的职责是切换某个顶点子树中所有房间的灯。这意味着，如果子树中某个房间的灯是开着的，他就应该关闭它；否则，他应该打开它。\n\n不幸的是（或者幸运的是），Danil 非常懒惰。他知道老板不会亲自检查他的工作，而是会通过 _Workforces_ 的私人消息向他发送任务。\n\n任务有两种类型：\n\n顶点 #cf_span[v] 的子树是指所有满足从该顶点到根的最短路径经过 #cf_span[v] 的顶点组成的集合。特别地，顶点 #cf_span[v] 本身也属于其子树。\n\nDanil 不打算履行他的职责。请你写一个程序，代替他回答老板的任务。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——树中顶点的数量。\n\n第二行包含 #cf_span[n - 1] 个空格分隔的整数 #cf_span[p2, p3, ..., pn]（#cf_span[1 ≤ pi < i]），其中 #cf_span[pi] 是顶点 #cf_span[i] 的父节点。\n\n第三行包含 #cf_span[n] 个空格分隔的整数 #cf_span[t1, t2, ..., tn]（#cf_span[0 ≤ ti ≤ 1]），其中 #cf_span[ti] 为 #cf_span[1] 表示顶点 #cf_span[i] 的灯是打开的，为 #cf_span[0] 表示关闭。\n\n第四行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 200 000]）——任务的数量。\n\n接下来的 #cf_span[q] 行是 _get v_ 或 _pow v_（#cf_span[1 ≤ v ≤ n]）——如上所述的任务。\n\n对于每个 _get v_ 任务，请输出子树 #cf_span[v] 中灯处于打开状态的房间数量。\n\n #cf_span(class=[tex-font-size-small], body=[The tree after the task _pow 1_.]) \n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——树中顶点的数量。\n第二行包含 #cf_span[n - 1] 个空格分隔的整数 #cf_span[p2, p3, ..., pn]（#cf_span[1 ≤ pi < i]），其中 #cf_span[pi] 是顶点 #cf_span[i] 的父节点。\n第三行包含 #cf_span[n] 个空格分隔的整数 #cf_span[t1, t2, ..., tn]（#cf_span[0 ≤ ti ≤ 1]），其中 #cf_span[ti] 为 #cf_span[1] 表示顶点 #cf_span[i] 的灯是打开的，为 #cf_span[0] 表示关闭。\n第四行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 200 000]）——任务的数量。\n接下来的 #cf_span[q] 行是 _get v_ 或 _pow v_（#cf_span[1 ≤ v ≤ n]）——如上所述的任务。\n\n## Output\n\n对于每个 _get v_ 任务，请输出子树 #cf_span[v] 中灯处于打开状态的房间数量。\n\n[samples]\n\n## Note\n\n  #cf_span(class=[tex-font-size-small], body=[The tree before the task _pow 1_.]) #cf_span(class=[tex-font-size-small], body=[The tree after the task _pow 1_.])","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \\{1, 2, \\dots, n\\} $ and vertex $ 1 $ is the root.  \nFor each vertex $ i \\in V $, let $ \\text{light}(i) \\in \\{0, 1\\} $ denote the state of the light in room $ i $:  \n- $ 1 $ if the light is on,  \n- $ 0 $ if the light is off.  \n\nFor any vertex $ v \\in V $, define $ S(v) \\subseteq V $ as the subtree rooted at $ v $:  \n$ S(v) = \\{ u \\in V \\mid \\text{the unique path from } u \\text{ to } 1 \\text{ passes through } v \\} $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200{,}000 $  \n2. Parent of vertex $ i $ (for $ i = 2, \\dots, n $) is given as $ p_i $, with $ 1 \\leq p_i < i $.  \n3. Initial light states: $ \\text{light}(i) \\in \\{0, 1\\} $ for all $ i \\in V $.  \n4. $ 1 \\leq q \\leq 200{,}000 $ tasks.  \n5. Each task is one of:  \n   - `pow v`: toggle the light state of every vertex in $ S(v) $.  \n   - `get v`: compute $ \\sum_{u \\in S(v)} \\text{light}(u) $.  \n\n**Objective**  \nProcess $ q $ tasks:  \n- For each `pow v`: update $ \\text{light}(u) \\leftarrow 1 - \\text{light}(u) $ for all $ u \\in S(v) $.  \n- For each `get v`: output $ \\sum_{u \\in S(v)} \\text{light}(u) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF877E","tags":["bitmasks","data structures","trees"],"sample_group":[["4\n1 1 1\n1 0 0 1\n9\nget 1\nget 2\nget 3\nget 4\npow 1\nget 1\nget 2\nget 3\nget 4","2\n0\n0\n1\n2\n1\n1\n0"]],"created_at":"2026-03-03 11:00:39"}}