|
nguyendinhanh1508 | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS ROOM STANDINGS CUSTOM INVOCATION
Codeforces Round 442 (Div. 2)
E. Danil and a Part-time Job Finished
time limit per test: 2 seconds
Practice
memory limit per test: 256 megabytes
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 n vertices, vertex 1 is the root of the tree. There is a room in each → Virtual participation
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. Virtual contest is a way to take part in past
contest, as close as possible to participation
on time. It is supported only ICPC mode for
Unfortunately (or fortunately), Danil is very lazy. He knows that his boss is not going to personally check the work. Instead, he will send virtual contests. If you've seen these
Danil tasks using Workforces personal messages. problems, a virtual contest is not for you -
solve these problems in the archive. If you
just want to solve some problem from a
There are two types of tasks: contest, a virtual contest is not for you -
solve this problem in the archive. Never use
1. pow v describes a task to switch lights in the subtree of vertex v. someone else's code, read the tutorials or
communicate with other person during a
2. 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 virtual contest.
to his boss using Workforces messages.
Start virtual contest
A 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.
→ Clone Contest to Mashup
Danil is not going to perform his duties. He asks you to write a program, which answers the boss instead of him.
You can clone this contest to a mashup.
Input Clone Contest
The first line contains a single integer n (1 ≤ n ≤ 200 000) — the number of vertices in the tree.
The second line contains n - 1 space-separated integers p2, p3, ..., pn (1 ≤ pi < i), where pi is the ancestor of vertex i.
→ Submit?
The third line contains n space-separated integers t1, t2, ..., tn (0 ≤ ti ≤ 1), where ti is 1, if the light is turned on in vertex i and 0 otherwise.
Language: GNU G++20 13.2 (64 bit, win
The fourth line contains a single integer q (1 ≤ q ≤ 200 000) — the number of tasks.
Choose
Choose File No file chosen
The next q lines are get v or pow v (1 ≤ v ≤ n) — the tasks described above. file:
Submit
Output
For each task get v print the number of rooms in the subtree of v, in which the light is turned on.
Example → Contest materials
input Copy
Announcement
4
1 1 1 Tutorial (en)
1 0 0 1
9
get 1
get 2
get 3
get 4
pow 1
get 1
get 2
get 3
get 4
output Copy
2
0
0
1
2
1
1
0
Note
The tree before the task pow 1.
The tree after the task pow 1.
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Mar/05/2025 01:06:39UTC+8 (i1).
Desktop version, switch to mobile version.
Privacy Policy
Supported by