{"problem":{"name":"「RiOI-2」equals","description":{"content":"给定一棵 $n$ 个结点，以 $1$ 为根的树，定义一个结点的深度 $d_i$ 表示它到根结点的简单路径上的结点个数。 你需要给每个结点黑白染色，满足黑色结点的深度和等于白色结点的深度和。设 $c_i = \\{0, 1\\}$ 分别代表编号为 $i$ 的结点为黑色或白色，那么这即 $\\displaystyle\\sum_{c_i=0}d_i=\\sum_{c_i=1}d_i$。 若无解，仅输出一行一","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9498"},"statements":[{"statement_type":"Markdown","content":"给定一棵 $n$ 个结点，以 $1$ 为根的树，定义一个结点的深度 $d_i$ 表示它到根结点的简单路径上的结点个数。\n\n你需要给每个结点黑白染色，满足黑色结点的深度和等于白色结点的深度和。设 $c_i = \\{0, 1\\}$ 分别代表编号为 $i$ 的结点为黑色或白色，那么这即 $\\displaystyle\\sum_{c_i=0}d_i=\\sum_{c_i=1}d_i$。\n\n若无解，仅输出一行一个整数 $-1$。\n\n## Input\n\n第一行一个正整数 $n$。\n\n接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$，表示树上编号为 $u_i$ 的结点与编号为 $v_i$ 的结点之间有一条边。保证给出的边不重复。\n\n## Output\n\n若有解，则输出一行 $n$ 个数 $c_1\\dots c_n$。\n\n若无解，仅输出一行一个整数 $-1$。\n\n**本题开启 Special Judge，只要你的方案满足条件或正确判断无解即可拿到本测试点的分数。**\n\n[samples]\n\n## Background\n\n在小树上坐落着一个幻想的城堡。这里是 E 国的领地，而小 E，则是 E 国之王。\n\n为了打造一个完美的 E 国，他需要明辨是非，走向正义。\n\n但是，他似乎有些太理想了。有时并没有一个完美的准则。是黑是白，谁能分辨？\n\n## Note\n\n### 样例解释\n\n对于第一组数据，每个结点的深度分别是 $d=[1,2,2,3,3,3]$。黑色结点的深度和为 $d_1+d_5+d_6=1+3+3=7$，白色结点的深度和为 $d_2+d_3+d_4=2+2+3=7$。它们相等，所以样例输出是正确的。可能的正确输出包括但不限于样例输出、`0 1 1 0 0 1`，`1 0 0 1 0 1` 等。\n\n### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n| $\\rm Subtask$ | 分值 | $n\\le $ | 特殊性质 |\n| :-----------: | :--: | :-----: | :------: |\n| $0$ | $5$ | $20$ | / |\n| $1$ | $15$ | $500$ | / |\n| $2$ | $20$ | $5\\times 10^3$ | / |\n| $3$ | $10$ | / | $n$ 为偶数 |\n| $4$ | $5$ | / | 树为菊花图（不保证根为菊花中心） |\n| $5$ | $5$ | / | 树为一条链（不保证根为链的端点） |\n| $6$ | $40$ | / | / |\n\n斜杠表示这一栏无特殊限制。\n\n对于 $100\\%$ 的数据，$1\\le n\\le 10^6$，$1\\le u_i,v_i\\le n$，输入数据构成一棵树。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9498","tags":["洛谷原创","Special Judge","O2优化","构造","洛谷月赛"],"sample_group":[["6\n1 2\n1 3\n2 4\n2 5\n2 6","0 1 1 1 0 0"],["5\n1 2\n1 3\n2 4\n2 5","-1"]],"created_at":"2026-03-03 11:09:25"}}