9.21集训

今天上午改题 毒瘤树剖题改过了

还透彻了割点与割边

割点：判断顶点U是否为割点，用U顶点的dnf值和它的所有的孩子顶点的low值进行比较，如果存在至少一个孩子顶点V满足low[v] >= dnf[u]，就说明顶点V访问顶点U的祖先顶点，必须通过顶点U，而不存在顶点V到顶点U祖先顶点的其它路径，所以顶点U就是一个割点。对于没有孩子顶点的顶点，显然不会是割点。

桥（割边）：low[v] > dnf[u] 就说明V-U是桥

下午考试

其中原题还是做对了，第一题是个假贪心，正解是暴力

第三题是树剖，在lca那里操作一下

第二题不会