{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"题面描述","value":{"format":"HTML","content":"\u003cp\u003e现有一棵 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003en\u003c/em\u003e\u003c/span\u003e 个点的树,点的编号从 \u003cspan class\u003d\"math inline\"\u003e1\u003c/span\u003e 起,树以 \u003cspan class\u003d\"math inline\"\u003e1\u003c/span\u003e 为根,每个点 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003ei\u003c/em\u003e\u003c/span\u003e 都一个颜色 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003ec\u003c/em\u003e\u003csub\u003e\u003cem\u003ei\u003c/em\u003e\u003c/sub\u003e\u003c/span\u003e,接下来有 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003em\u003c/em\u003e\u003c/span\u003e 个询问,每次询问以 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003ev\u003c/em\u003e\u003csub\u003e\u003cem\u003ej\u003c/em\u003e\u003c/sub\u003e\u003c/span\u003e 为根的子树中,求有多少种颜色,这些颜色在子树中出现的次数至少为 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003ek\u003c/em\u003e\u003csub\u003e\u003cem\u003ej\u003c/em\u003e\u003c/sub\u003e\u003c/span\u003e。\u003c/p\u003e"}},{"title":"输入格式","value":{"format":"HTML","content":"\u003cp\u003e第一行两个整数 \u003cspan class\u003d\"math inline\"\u003e2 ≤ \u003cem\u003en\u003c/em\u003e ≤ 100 000\u003c/span\u003e, \u003cspan class\u003d\"math inline\"\u003e1 ≤ \u003cem\u003em\u003c/em\u003e ≤ 100 000\u003c/span\u003e,如题面描述。\u003c/p\u003e\n\u003cp\u003e接下来一行有 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003en\u003c/em\u003e\u003c/span\u003e 个整数,\u003cspan class\u003d\"math inline\"\u003e1 ≤ \u003cem\u003ec\u003c/em\u003e\u003csub\u003e\u003cem\u003ei\u003c/em\u003e\u003c/sub\u003e ≤ 100 000\u003c/span\u003e,表示第 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003ei\u003c/em\u003e\u003c/span\u003e 个点的颜色。\u003c/p\u003e\n\u003cp\u003e接下来 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003en\u003c/em\u003e − 1\u003c/span\u003e 行,每行两个整数 \u003cspan class\u003d\"math inline\"\u003e1 ≤ \u003cem\u003eu\u003c/em\u003e\u003csub\u003e\u003cem\u003ei\u003c/em\u003e\u003c/sub\u003e ≤ \u003cem\u003en\u003c/em\u003e\u003c/span\u003e, \u003cspan class\u003d\"math inline\"\u003e1 ≤ \u003cem\u003ev\u003c/em\u003e\u003csub\u003e\u003cem\u003ei\u003c/em\u003e\u003c/sub\u003e ≤ \u003cem\u003en\u003c/em\u003e\u003c/span\u003e,表示树上第 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003ei\u003c/em\u003e\u003c/span\u003e 条边的两个点。\u003c/p\u003e\n\u003cp\u003e接下来 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003em\u003c/em\u003e\u003c/span\u003e 行,每行两个整数 \u003cspan class\u003d\"math inline\"\u003e1 ≤ \u003cem\u003ev\u003c/em\u003e\u003csub\u003e\u003cem\u003ej\u003c/em\u003e\u003c/sub\u003e ≤ \u003cem\u003en\u003c/em\u003e\u003c/span\u003e, \u003cspan class\u003d\"math inline\"\u003e1 ≤ \u003cem\u003ek\u003c/em\u003e\u003csub\u003e\u003cem\u003ej\u003c/em\u003e\u003c/sub\u003e ≤ 100 000\u003c/span\u003e,表示第 \u003cspan class\u003d\"math inline\"\u003e\u003cem\u003ej\u003c/em\u003e\u003c/span\u003e 个询问。\u003c/p\u003e"}},{"title":"输出格式","value":{"format":"HTML","content":"\u003cp\u003e对每个询问输出一个答案。\u003c/p\u003e"}},{"title":"样例","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e8 5\u003cbr\u003e1 2 2 3 3 2 3 3\u003cbr\u003e1 2\u003cbr\u003e1 5\u003cbr\u003e2 3\u003cbr\u003e2 4\u003cbr\u003e5 6\u003cbr\u003e5 7\u003cbr\u003e5 8\u003cbr\u003e1 2\u003cbr\u003e1 3\u003cbr\u003e1 4\u003cbr\u003e2 3\u003cbr\u003e5 3\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e2\u003cbr\u003e2\u003cbr\u003e1\u003cbr\u003e0\u003cbr\u003e1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4 1\u003cbr\u003e1 2 3 4\u003cbr\u003e1 2\u003cbr\u003e2 3\u003cbr\u003e3 4\u003cbr\u003e1 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"样例解释","value":{"format":"HTML","content":"\u003cp\u003e第一个样例:前3个询问均对以 \u003cspan class\u003d\"math inline\"\u003e1\u003c/span\u003e 为根的子树进行,出现至少 2 次的有颜色 \u003ccode\u003e2\u003c/code\u003e 和 颜色 \u003ccode\u003e3\u003c/code\u003e;出现至少 3 次的有颜色 \u003ccode\u003e2\u003c/code\u003e 和 颜色 \u003ccode\u003e3\u003c/code\u003e;出现至少 4 次的有颜色 \u003ccode\u003e3\u003c/code\u003e。第4个询问以 \u003cspan class\u003d\"math inline\"\u003e2\u003c/span\u003e 为根的子树,所有点的颜色中,没有出现至少 3 次的颜色。第5个询问以 \u003cspan class\u003d\"math inline\"\u003e5\u003c/span\u003e 为根的子树,出现至少 3 次的颜色有颜色 \u003ccode\u003e3\u003c/code\u003e。\u003c/p\u003e\n"}}]}