Packages - MarisaOJ: Marisa Online Judge

Packages

Time limit: 1000 ms
Memory limit: 256 MB
For a tree with n vertices, each vertex can be either white or black, initially all vertices are white. There are q queries, each falling into one of two forms: - 1u: All vertices on the path from the root to u will become black. - 2u: All vertices in the subtree rooted at u will become white. For each query, determine the number of vertices that change color after the query is executed. ### Input - The first line consists of two integers n,q. - The next n−1 lines, each containing two integers u,v, indicating an edge between u and v. - The next q lines, each representing a query in the specified format. ### Output - After each query, print the number of vertices that change color. ### Constraints - 1≤n,q≤105. - 1≤u,v≤n. ### Sample test Input 64121334352612231423 Output: 2022