这是本文档旧的修订版！
目录
Summer Tranning Week 3
比赛简记
Max.D.
专题
本周暂无
比赛
主要是两场CF，一场涨了一场跌了，基本等于没打（苍天啊）
题目
Hardict
专题
比赛
题目
MountVoom
专题
无
比赛
因为没有cf div.1，所以一直在慢慢补cf的和牛客的题。
题目
无
个人总结
陈铭煊 Max.D.
要多加强思维训练
龙鹏宇 Hardict
肖思炀 MountVoom
感觉还行，补题应该再积极一点。
本周推荐
陈铭煊 Max.D.
来源：
Codeforces 660（Div.2）C . Uncle Bogdan and Country Happiness
发现自己CF面对不熟悉的问题，思维总是很慢，写下这道题主要是给自己引以为戒的。这周开始尽量多vp，提高自己的思维能力。
标签：
思维，树的遍历
题意：
给你$n$个城市和$n-1$条道路，城市$i$生活了$p_i$个人，他们都工作在城市$1$，工作结束要返回各自城市，每个人回家时有的有好心情，有的有坏心情，经过一条边时，某些好心情的人会变成坏心情。定义一个城市的开心指数$h_i$为经过（或者到达）的好心情的人的数量减去坏心情的人的数量。出所有$h_i,p_i$，询问是否存在这样的可能情况。$1\le t\le 10000,1\le n\le 10^5,1\le m=\sum p_i\le 10^9,-10^9\le h^i\le 10^9, \sum n\le 2*10^5$。
题解：
用一个子树中$p_i$的和，以及$h_i$，可以求出经过$i$的开心的人数和不开心的人数，当然这个人数要在$[0,p_i]$中。这是第一个条件。由于开心的人数递减，所以所有儿子的开心人数之和不会多于父亲。这是第二个条件。
评论：
当时赛场上莫名奇妙想了一些多余的条件，比如儿子的$h$之和不超过子树中$p$之和$-p_i$，这个显然是很多余的，因为第一个条件满足这个肯定满足。第二个条件当时一直在想不开心人数，居然没有稍微反着一点。这种题目写了一个小时，我也是很自闭。
龙鹏宇 Hardict
来源：
标签：
题意：
题解：
评论：
肖思炀 MountVoom
来源：
标签：
博弈，贪心
题意：
给了n个正整数，两人轮流从中取数，最终取得的数异或起来大的人获胜，一样则平局，双方均采取最优策略，求比赛结果。
题解：
设n个数异或起来的答案为s，先手的答案为x，后手的答案为y。
那么平局当且仅当x=y即s=0。
当s=0时，考虑s最高位的1，设这一位为p，x和y在这一位一定是一个1和一个0，而更高位无论怎么选x和y一定是相等的，更低位无论怎么选不影响最终结果。
所以只需要考虑原数组的第p位的0和1的个数即可，而1的个数一定是奇数，设为m，想胜利的人需要拿到奇数个1。
首先，如果有且仅有m个1，且$(m+1)/2$为偶数时先手必败，因为先手只可能拿到偶数个1。
假设$(m+1)/2$是一个奇数，如$m = 5, (m + 1) / 2 = 3$，此时先手必胜，只要先手先拿走一个1，然后后手拿什么先手就拿什么，如果后手拿走了最后一个0，先手拿1即可把状态变为刚才说的先手必败的状态。
假设$(m+1)/2$是一个偶数，那么考虑0的个数，如果0的个数是奇数，那么先手必胜，因为先手可以先拿走一个0，接下来后手拿什么先手就拿什么，这样后手一定会拿到更多的1也就是偶数个1。如果0的个数是偶数，那么就成了刚才说的情况，不过变成了先手拿什么后手就拿什么，这样先手就一定会拿到更多的1，此时先手必败。
评论：
关键在于考虑到两个人的答案异或起来等于所有数异或起来，这样就只用考虑某一位的1和0而不用考虑所有位置，一下子简化了问题。
而比较大小的关键在于拿到的1的个数，所以进行相应的分类讨论。
