http://acm.hdu.edu.cn/showproblem.php?pid=5606 题意：一棵树，边权为0或者1，问对于每个点，距离它最近的点（包括自身）的个数是多少。输出将所有点的答案异或后的值。 思路：由于包括自身，自己与自己距离为0，那么最近的点一定也距离为0，所以就是找对于每个点与它相连的边权为0 的点的个数**。建图的时候可以不管边权为1的点。。因为这样的点不会对任何点的答案有贡献。**正解貌似是冰茶几。。我就是dfs搞了下。。找到每一个联通快的点数。。然后把某个联通快的所有点的答案都更新成点的个数。。。 /* *********************************************** …

http://codeforces.com/contest/526/problem/B 题意：有一棵完全二叉树。每条边上有一定数量的路灯。问最少需要添加多少个路灯。使得根节点道叶子节点的每一条路径上的路灯数量一样。 思路：同叶子节点网上更新即可。 /* *********************************************** Author :111qqz Created Time :2015年12月11日 星期五 16时57分27秒 File Name :code/cf/problem/526B.cpp ************************************************ */ …

http://codeforces.com/contest/277/problem/A 题意：有n个人，每个人会一定数目的语言（可能为0），一个人学一门语言的代价为1，人和人之间沟通可以通过任意个中间人翻译。问最少的代价使得这n个人可以相互沟通。 思路：建图方式如下：第i个人会语言j，那么连上i和j+n。然后跑一遍dfs,使得1..n这n个点都被访问过。 结果wa4...觉得算法没问题。。看了官方题解。。发现果然有情况没有考虑到。如果所有的人都什么语言都不会的话，那么答案是不能-1的。。因为。。语言和语言之间不能连边。。改了之后A了。。有点开心。。 /* …

http://codeforces.com/problemset/problem/217/A 题意：有n个雪漂（那是啥？，从某个雪漂出发走直线，只有到达另一个雪飘才能停下来。问最少需要添加多少个雪漂，才能使得可以到达任何一个雪漂。 思路：横坐标相同或者纵坐标相同的两个点之间是可以到达的。先O(N2)扫一遍建图。记录这个森林中数的个数为cnt,cnt-1即为答案。因为对于任意两个不能相互到达的点。我们只需要再来一个雪漂就可以使得这两个点相互到达。 一遍AC，有点爽。 /* *********************************************** Author :111qqz Created Time :2015 …

http://codeforces.com/contest/445/problem/B 题意：一共有n种化学药品。m对关系，每对关系表示为x,y表示x和y相互反应。初始容器的danger值为1，当向容器中加入一个化学药品A,如果容器中存在化学药品和A反应，那么容器的danger值翻倍。否则不变。问一个最优的放置药品的顺序。 思路：容易发现。如果两个药品相互反应就连一条边。实际上这些药品构成了一个森林。而一个节点只要不是树的根节点，那么它在任何位置，对答案的贡献度都是*2.反过来说。所有的节点，只有根节点是对答案没有贡献的。那实际上，我们只需要dfs一遍，得到树的数目，用n减去树的数目，就是对答案有贡献的点的数目。 要注意开long …

http://codeforces.com/contest/580/problem/C 题意：给出一棵树。每个叶子节点上有一个饭店。某些节点上有cat.现在问从根节点出发可以到达多少个饭店，保证在到达饭店的路径中补连续遇到m个以上的cat. 思路：建图，然后dfs..判断为叶子节点（饭店）的方法是某个点的叶子节点数为0. /* *********************************************** Author :111qqz Created Time :2015年12月05日 星期六 10时17分01秒 File Name :580C.cpp …

http://codeforces.com/problemset/problem/115/A 题意：给出n个人之间的上级下级关系。问如何分得最少的组，使得没一组中的人不存在上下级关系。 思路：用树的观点来考虑会很容易。可以看成给了一棵森冷。对于不同的树的相同层的点，不存在上下级关系，可以放在一个group.对于同一棵树，每一层要单独放一个group.所以答案是所有树的深度的最大值。 /* *********************************************** Author :111qqz Created Time :2015年12月04日 星期五 21时31分38秒 File Name …