两道笔试题

树上染色

给定一颗树，树上节点被分配给红色与白色，每次操作你可以更改任意一个节点的颜色，求使红色节点与白色节点不相邻的最小操作次数

Example:

Input:

4
RWWW
1 2
2 3
2 4

第一行为节点数目，4代表有(1 2 3 4)四个节点。第二行为节点目前染色情况，R代表红色，W代表白色，之后为节点间的边。

即：

               |4 W|
              /
|1 R| -- |2 W| -- |3 W|

Output:

2

可能方法：将树转化为二分图，面试不知道哪一步写错，只过了15%样例。

排列权值和

定义一个数列的权值为其相邻元素之积为奇数的个数，例如：[6, 5, 1, 3, 2, 4]，其权值为 2，即5 * 1 = 5， 1 * 3 = 3，一共两个。
给定一个数字 n，求出其 1 到 n 的所有全排列的权值之和。

Example:

Input:

3

Output:

4

解释: 1 2 3的全排列中权值为 1 的有(1 3 2), (3 1 2), (2 3 1), (2 1 3)，其余权值均为 0，故结果为 4。