冰冻三尺 非一日之寒

摘要： 题意： 求树上最长上升路径 解析： 树状数组版： 998ms edge[u][w] 代表以u为一条路的终点的小于w的最长路径的路的条数 · 那么edge[v][w] = max(edge[u][w-1]) + 1; 因为w最小是0 所以所有的w都+1 主席树： 108ms 每棵树都建立100000个 阅读全文

摘要： 例题：POJ-2104 求区间第k大 sum代表当前数是第几大 对每个数建一棵树 当前树的sum 继承自上一颗树的sum 从祖先到当前数的位置 sum++ 如果前面的数中没有比当前数大的数 sum++后为1 即为第一大的数 而其它小的数的sum在从祖先到当前数的位置寻找时顺便sum++更新 阅读全文

摘要： 题意： 求出简单环的所有边，简单环即为边在一个环内 解析： 求出点双连通分量，如果一个连通分量的点数和边数相等，则为一个简单环 点双连通分量 任意两个点都至少存在两条点不重复的路径 即任意两条边都至少存在于一个简单环中 那么我们要求的那个简单环 是不是就是点双连通分量的特殊情况 即任意两条边只存在于 阅读全文

摘要： 题意： 构造一个无向图，使得无向图里的所有点的度数 所组成的集合 即为给出的几个数 解析： 题中的数是以上升的顺序给出的， 我们对于dn+1个数进行处理，对于当前数i，有两个操作 1、向后边的所有点连边 称为主动连边 2、跳过该数 即不向后边的点连边，称为被动连边 设tot = dn+1， l = 阅读全文

摘要： 题意： 就是找出所有环的个数， 但这个环中的每个点都必须只在一个环中 解析： 在找环的过程中 判断度数是否为2就行。。。emm。。。 阅读全文

摘要： 题意： n个点 有n-1条边 去除最多的边 使得每个连通块点的个数为偶数 解析： 点的个数为奇数的时候肯定不行，输出-1 当为偶数时，随便选一个点作为根dfs搜一下 如果一个点的子树中点的个数为偶数 则断开和父结点的边即可 统计一共有多少个即可 为什么要是子树中点的个数。。。不从根开始统计。。。画画 阅读全文

摘要： 题意： 问至少加几条边 能使点s可以到达所有的点 解析： 无向图的连通分量意义就是 在这个连通分量里 没两个点之间至少有一条可以相互到达的路径 所以 我们符合这种关系的点放在一起， 由s向这些点的任意一个连边即可 即为求除s所在的连通分量以外的 入度为0的连通分量 阅读全文

摘要： 双向bfs 注意数很大 用map来存 然后各种难受。。。。 阅读全文

摘要： 题意： 就是求桥最多的一条路 解析： 先求连通分量的个数 然后缩点建图 求直径即可 阅读全文

摘要： 题意： 就是让构造一个直径为d的树 每个结点的度数不能超过k 解析： 先构造出一条直径为d的树枝 然后去遍历这条树枝上的每个点 为每个点在不超过度数和直径的条件下添加子嗣即可 阅读全文