四种实现实现模式长处毛病邻接矩阵实现简略，可求任意顶点的出度和入度在存储稠密图时会造成空间节约邻接表应用数组链表实现，不会造成空间节约不能同时求出任意顶点的出度和入度，除非同时构建邻接表和逆邻接表。对边进行操作时须要操作两次十字链表应用数组链表实现，不会造成空间节约，能够求出某个顶点的入度和出度…

P3258 [JLOI2014]松鼠的新家：[链接]树剖+线段树 {代码…} 树上差分 {代码…}

工夫复杂度为O(n)，最坏状况下为一条链；求4和6的最近公共先人：首先建设一个bool类型的数组用来标记4或者6的先人，比方，4的先人是2,1（从下往上顺次遍历并标记），那就将2,1标记为1，之后标记6的先人，在标记过程中如果遇到已被标记的先人，那么这个先人就是4和6的公共先人，在本例中为1。