{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e♔♕♖♗♘♙♚♛♜♝♞♟\u003c/p\u003e\n\n\u003cp\u003e安东正在他的花园里种树。如果你忘了,树是一个连通的无环无向图。\u003c/p\u003e\u003cp\u003e树中有\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e个顶点,每个顶点都被涂成黑色或白色。安东不喜欢多彩的树,所以他想改变树,使得所有顶点都是同一种颜色(黑色或白色)。\u003c/p\u003e\u003cp\u003e为了改变颜色,安东只能使用一种类型的操作。我们将其表示为\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003epaint\u003c/i\u003e(\u003ci\u003ev\u003c/i\u003e)\u003c/span\u003e,其中\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e是树的某个顶点。这个操作会改变所有顶点\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e的颜色,使得从\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e到\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e的最短路径上的所有顶点都有相同的颜色(包括\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e和\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e)。例如,考虑下面的树\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/8e4c5b941260111688903047dd1add0b?v\u003d1711115330\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003e并应用操作\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003epaint\u003c/i\u003e(3)\u003c/span\u003e后得到以下结果:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/a035352d5d9d2b2ca6c50e9997757d9b?v\u003d1711115330\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003e安东想知道需要执行的最少操作次数,才能使所有顶点的颜色相同。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含一个整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 200 000\u003c/span\u003e)— 树中顶点的数量。\u003c/p\u003e\u003cp\u003e第二行包含\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e个整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ecolor\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ecolor\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 1\u003c/span\u003e)— 顶点的颜色。 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ecolor\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u003d 0\u003c/span\u003e表示第\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e个顶点最初被涂成白色,而\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ecolor\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u003d 1\u003c/span\u003e表示它最初被涂成黑色。\u003c/p\u003e\u003cp\u003e然后是\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e行,每行包含一对整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e和\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e)— 相连边对应的顶点索引。保证所有对\u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e都是不同的,即没有重复的边。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数— 安东需要应用的最少操作次数,才能使树中所有顶点都是黑色或白色。\u003c/p\u003e"}},{"title":"示例 1","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\u003e11\n0 0 0 1 1 0 1 0 0 1 1\n1 2\n1 3\n2 4\n2 5\n5 6\n5 7\n3 8\n3 9\n3 10\n9 11\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 2","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\n0 0 0 0\n1 2\n2 3\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,树与图片中的树相同。如果我们首先应用操作\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003epaint\u003c/i\u003e(3)\u003c/span\u003e,然后应用\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003epaint\u003c/i\u003e(6)\u003c/span\u003e,树将变成完全黑色,所以答案是\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e在第二个示例中,树已经是白色的,所以不需要应用任何操作,答案是\u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e。\u003c/p\u003e"}}]}