树与统计 致远15级ACM班 孔冰玉.

Presentation on theme: "树与统计 致远15级ACM班 孔冰玉."— Presentation transcript:

1 树与统计 致远15级ACM班 孔冰玉

2 树的定义 无向图 N个点N-1条边的连 通图 没有环的连通图 任意两点之间有且 仅有一条路径的图

3 相关定义 根（A） 叶子（#） 父子关系 祖先关系 兄弟关系 子树

4 节点深度

5 储存图的方式 邻接矩阵 存在边(u, v, w), map[u][v] = w 邻接表 存在边(u, v, w),
count_edge[u] ++; map[u][count_edge[u] ] = v; Value[u][count_edge[u] ] = w;

6 子树的Size size[now] = sigma( size[ sons of now ] ) + 1

7 辣鸡的机考题 N <= vector 储存

8 试试看能不能理解的奇怪的题目 POJ 2342 (http://poj.org/) ->小写QwQ
有N个职员在同一个公司，人与人之间有上司和下属的关系， 除BOSS之外每个人有且仅有一个直接上司，且除BOSS外， 每个人都存在一条关系链表示BOSS是他的直接或间接上司。 公司要举行一个PARTY，需要邀请一些职员到场，每个职员 都会有一个重要程度值，这场PARTY的重要程度值就是所有 被邀请职员的重要程度值之和。若一个职员X被邀请了，那 就不能邀请他的直接上司，否则PARTY就不能轻松愉悦了。 问这场PARTY的重要程度最大是多少。

9 试试看能不能理解的奇怪的题目 职员是节点，上司和下属的关系转换为父子关系 建立树形图 考虑以编号为x的职员为根的子树
F[x][0]表示，在不邀请编号为x的职员的情况下，在这棵子 树内选一些职员邀请，能获得的最大值（不考虑不在这棵子 树内的职员被邀请的情况） F[x][1]表示，在邀请编号为x的职员的情况下，在这棵子树 内选一些职员邀请，能获得的最大值（不考虑不在这棵子树 内的职员被邀请的情况）

10 试试看能不能理解的奇怪的题目 如果不邀请职员x参加party，那他的下属可以被邀请，也可 以不被邀请
F[x][0] = sigma [ max(f[sony of x][1], f[sony of x][0]) ] 如果邀请职员x参加party，那一定不能邀请他的下属 F[x][1] = sigma ( f[sony of x][0] )

11 有关二分 制作一个饼干需要n种原料，对于原料i需要a[i]，现在已有b[i] 的i原料，同时Apollinar还有k的万用原料，万用原料能变成 任意一种原料。现在让你求出最多能制作多少饼干  N<10^5, 其他数据<10^9 Codeforces 760d2

12 有关二分 高考结束后，同学们大都找到了一份临时工作，渴望挣得一些零用钱。从今天起，Matrix67将连续工作N天(1<=N<= )。每一天末他可以领取当天及前面若干天里没有领取的工资，但他总共只有M(1<=M<=N)次领取工资的机会。Matrix67已经知道了在接下来的这N天里每一天他可以赚多少钱。为了避免自己滥用零花钱，他希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。注意Matrix67必须恰好领工资M次，且需要将所有的工资全部领走（即最后一天末需要领一次工资）。 输入数据 第一行输入两个用空格隔开的正整数N和M 以下N行每行一个不超过10000正整数，依次表示每一天的薪水。 输出数据 输出领取到的工资的最大值最小是多少。

13 有关二分 平面上有n个点，以坐标形式给出，要求用三个边长相等的 正方形覆盖所有点（在边界上也算被覆盖），求这些正方形 边长的最小值。
考试用的oj 1522， N <= 20000， 坐标在int范围内。