{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003ewls 有三棵树,树上每个节点都有一个值 $a_i$,现在有 2 种操作:\u003cbr\u003e1. 将一条链上的所有节点的值开根号向下取整;\u003cbr\u003e2. 求一条链上值的和;\u003cbr\u003e链的定义是两点之间的最短路。\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第一行两个数 $n$, $q$ 分别代表树上点的数量和操作数量。\u003cbr\u003e第二行 $n$ 个整数,第 $i$ 个数代表第 $i$ 个点的值 $a_i$。\u003cbr\u003e接下来 $n$ $-$ $1$ 行, 每行两个整数 $u$, $v$ 代表 $u$,$v$ 之间有一条边。数据保证点两两联通。\u003cbr\u003e接下来 $q$ 行,每行有个整数 $op$, $u$, $v$,$op$ \u003d 0 表示将 $u$, $v$ 这条链上所有的点的值开根号向下取整,$op$ \u003d 1表示询问 $u$,$v$ 这条链上的值的和。\u003cbr\u003e1 ≤ $n$, $q$ ≤ 100, 000\u003cbr\u003e0 ≤ $a_i$ ≤ 1, 000, 000, 000"}},{"title":"Output","value":{"format":"HTML","content":"对于每一组 $op$ \u003d 2 的询问,输出一行一个值表示答案。"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e4 4\r\n2 3 4 5\r\n1 2\r\n2 3\r\n2 4\r\n0 3 4\r\n0 1 3\r\n1 2 3\r\n1 1 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}