All submissions for this problem are available.Given a rooted tree consisting of N nodes rooted at node number 1, and a value val[i] associated with each node i. We need to state if it is possible to select a subset of nodes such that if X is the set of selected nodes and Y is the set of not selected nodes, no two nodes a, b should satisfy any of the following properties:
- a belongs to X, b belongs to X and val[a]*val[b]%N = 1
- a belongs to Y, b belongs to Y and val[a]*val[b]%N = 1
- a belongs to X, b belongs to X, a is an ancestor of b and gcd(val[a],val[b]) > 1
Report if it is possible to select such a subset of nodes.
Input Format:First line contains a single integer, the number of test cases T.
Inputs for T test cases follow.
First line for each test case contains a single integer, the number of nodes N.
The next line contains N space seperated integers, ith number denoting val[i].
The next N-1 lines contain 2 space seperated integers each: x y, denoting that there is an edge between the nodes x and y.
Output Format:Print T lines, one for each test case.
If it is possible to select such a subset of nodes, print "Yes", else print "No" (Without Quotations).
- 1<= T <= 200000
- 1<= N <= 200000
- Sum of all N over all test cases <= 200000
- 1<= val[i] < N
- 1<= x, y <= N
- x != y
1 3 6 5 4 3 5
1 1 2
|Tags||2sat, auxiliary-tree, gvaibhav21, inso2018, insomnia18|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions