{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eJohn has got a tree with N vertices. The vertices are numbered from 1 to N. He considers vertex 1 as the root of the tree. Each vertex of the tree contains a character C.\u003c/p\u003e\r\n\u003cp\u003eNow John is doing a weird experiment with this tree.\u003c/p\u003e\r\n\u003cp\u003eHe often changes the character of a node in the tree and then sometimes he randomly selects a node v and tries to form a palindrome with all the characters in the subtree of node v.\u003c/p\u003e\r\n\u003cp\u003eBut since John is very busy man and has a lot of other important experiments to do he needs your help on this one.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eFirst line of the input contains an integer N (1 \u0026lt;\u003d N \u0026lt;\u003d 100000) denoting the number of vertices.\u003c/p\u003e\r\n\u003cp\u003eNext N-1 lines contains two integers A and B (1 \u0026lt;\u003d A, B \u0026lt;\u003d N) which means there is an edge between vertex A and B.\u003c/p\u003e\r\n\u003cp\u003eNext line contains a string of length N. The i\u003csup\u003eth\u003c/sup\u003e character of this string denotes the character in node i.\u003c/p\u003e\r\n\u003cp\u003eThen there will be an integer M (1 \u0026lt;\u003d M \u0026lt;\u003d 100000) in a separate line denoting the number of queries. Next M lines will contain a query.\u003c/p\u003e\r\n\u003cp\u003eEach query will be in one of the following form:\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003e0 x C\u003c/strong\u003e: which means the character of node x has been changed to C.\u003c/p\u003e\r\n\u003cp\u003e\u003cstrong\u003e1 x\u003c/strong\u003e: which means you are asked to answer if a palindrome can be formed with all the characters in the sub tree of node x. There will be at least one query of this type.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each query of the form\u0026nbsp;\u003cstrong\u003e“1 x”\u003c/strong\u003e print “YES” if a palindrome can be formed with all the characters in subtree of node x. Otherwise print “NO” (without the quotes).\u003c/p\u003e\r\n\u003cp\u003eAll the characters in the input will be small letters of English alphabet, i.e. a, b, c ... x, y, z.\u003c/p\u003e\r\n\u003cp\u003eSee sample input / output for details.\u003c/p\u003e\r\n\u003ch3\u003eSample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7\r\n5 4\r\n1 5\r\n6 3\r\n1 7\r\n5 6\r\n6 2\r\nabdaabc\r\n7\r\n1 1\r\n1 5\r\n1 3\r\n0 7 a\r\n1 1\r\n0 4 z\r\n1 5\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNO\r\nYES\r\nYES\r\nYES\r\nNO\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003eIn the 2\u003csup\u003end\u003c/sup\u003e\u0026nbsp;query, the formed palindrome can be “badab” or “abdba”.\u003c/p\u003e\r\n\u003cp\u003eIn the 3\u003csup\u003erd\u003c/sup\u003e\u0026nbsp;query, there is only 1 character “d”, which is a palindrome.\u003c/p\u003e\r\n\n\u003c/div\u003e"}}]}