Chef and Tree
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef likes trees a lot. Now he thinking about one interesting problem on trees. He finds the following problem interesting, and you?
Given a tree T and Q queries to it. Tree T has N nodes numbered from 1 to N. Each node v has a value Av associated with it. Queries can be one of three types.
- 1 u v - reverse the values on the path between vertices u and v.
- 2 ul ur vl vr - print "Yes" if all the values on the path from ul to ur are exactly same as that of path from vl to vr, and "No" otherwise. It is ensured that length of both the paths are same.
- 3 ul ur vl vr - Copy all values on path from ul to ur and insert them into the path from vl to vr. It is ensured that length of both the paths are same.
The first line contains two integers N and Q.
The second line contains N space-separeted integers denoting Av - the values associated with nodes.
Next N-1 lines contains two space-separeted integers u, v denoting the nodes connected by an edge.
Next Q lines contains queries as described above.
For each query of second type output your answer in a single line.
- 1 ≤ N, Q ≤ 105
- 1 ≤ Ai ≤ 103
- 1 ≤ u, v, ul, ur, vl, vr ≤ N
- Subtask 1: (21 pts) N, Q ≤ 25000.
- Subtask 2: (79 pts) Original constraints.
Input: 5 8 1 2 3 4 5 1 2 1 3 2 4 2 5 2 1 3 1 2 3 1 1 2 2 3 1 1 3 3 2 1 3 1 2 1 2 5 2 1 3 1 2 1 2 5 2 1 3 1 2 Output: No Yes No Yes
|Tags||aug16, decomposition, hard, heavy-light, mgch, segment-tree|
|Time Limit:||9 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.