luogu#P9498. 「RiOI-2」equals
「RiOI-2」equals
题目背景
在小树上坐落着一个幻想的城堡。这里是 E 国的领地,而小 E,则是 E 国之王。
为了打造一个完美的 E 国,他需要明辨是非,走向正义。
但是,他似乎有些太理想了。有时并没有一个完美的准则。是黑是白,谁能分辨?
题目描述
给定一棵 个结点,以 为根的树,定义一个结点的深度 表示它到根结点的简单路径上的结点个数。
你需要给每个结点黑白染色,满足黑色结点的深度和等于白色结点的深度和。设 分别代表编号为 的结点为黑色或白色,那么这即 。
若无解,仅输出一行一个整数 。
输入格式
第一行一个正整数 。
接下来 行,每行两个整数 ,表示树上编号为 的结点与编号为 的结点之间有一条边。保证给出的边不重复。
输出格式
若有解,则输出一行 个数 。
若无解,仅输出一行一个整数 。
本题开启 Special Judge,只要你的方案满足条件或正确判断无解即可拿到本测试点的分数。
6
1 2
1 3
2 4
2 5
2 6
0 1 1 1 0 0
5
1 2
1 3
2 4
2 5
-1
提示
样例解释
对于第一组数据,每个结点的深度分别是 。黑色结点的深度和为 ,白色结点的深度和为 。它们相等,所以样例输出是正确的。可能的正确输出包括但不限于样例输出、0 1 1 0 0 1
,1 0 0 1 0 1
等。
数据规模与约定
本题采用捆绑测试。
分值 | 特殊性质 | ||
---|---|---|---|
/ | |||
/ | 为偶数 | ||
树为菊花图(不保证根为菊花中心) | |||
树为一条链(不保证根为链的端点) | |||
/ |
斜杠表示这一栏无特殊限制。
对于 的数据,,,输入数据构成一棵树。