Tree query
Tag(s):

## Advanced Data Structures, Algorithms, Data Structures, Segment Trees, Trees

Problem
Editorial
Analytics

A tree is a simple graph in which every two vertices are connected by exactly one path. You are given a rooted tree with $n$ vertices and a lamp is placed on each vertex of the tree.

You are given $q$ queries of the following two types:

• $1\ v$: You switch the lamp placed on the vertex $v$, that is, either from On to Off or Off to On.
• $2\ v$: Determine the number of vertices connected to the subtree of $v$ if you only consider the lamps that are in On state. In other words, determine the number of vertices in the subtree of $v$, such as $u$, that can reach from $v$ by using only the vertices that have lamps in the On state.

Note: Initially, all the lamps are turned On and the tree is rooted from vertex number $1$.

Input format

• First line: Two integers $n$ and $q$ denoting the number of vertices and queries
• Next $n -1$ lines: Two number $a_i$ and $b_i$ denoting an edge between the vertices $a_i$ and $b_i$
• Next $q$ lines: Two integers $t_i$ and $v_i$, where $t_i$ is the type of the $i^{th}$ query

Note: It is guaranteed that these edges form a tree rooted from vertex $1$.

Output format
For every query of type 2, print the answer in a single line.

Constraints

$1 \leq n, q \leq 5 \times 10^{5}\\ 1 \leq a_i, b_i \leq n\\ 1 \leq t_i \leq 2\\ 1 \leq v_i \leq n$

SAMPLE INPUT
5 4
1 2
2 3
1 4
4 5
1 3
2 2
1 3
2 2

SAMPLE OUTPUT
1
2

Explanation

Obviously the answer now for vertex $2$ is $1$

Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

March Easy '20

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Basic Math
• Algorithms > Dynamic Programming
• Basic Programming > Implementation