给出一张$n$个点$m$条边的无向联通图，现在要求在这张图中要么找到一个至少有$\lceil \frac{n}{2} \rceil$个点的路径，要么找到一个至少包含$\lceil \frac{n}{2} \rceil$个点集合，要求点的个数为偶数，每两个节点分为一组，每个节点只在一组，且任意两组一共四个点所生成的子图中边数不超过两条。$(2 \le n \le 5\cdot 10^5, 1 \le m \le 10^6)$

构建dfs生成树，如果最深的节点深度$\ge \lceil \frac{n}{2} \rceil$，则已经找到一条合法路径。否则所有点的深度均小于$\lceil \frac{n}{2} \rceil$，我们只需要将同一深度的数个点两两分为一组，如果是奇数就扔掉那一个，这样最多扔掉$\lfloor\frac{n}{2} \rfloor$个点，且这些组合显然满足条件（由dfs生成树的性质）。

给出一张$n$个点$m$条边的无向图，其中有$k$个点是关键点，每条边有一个权值$w_i$，每个点有一个权值$c_i$。你可以给每条边定向，也可以让它保持无向，设所有保持无向的边集为$U$，设所有关键点能都到达的点组成的点集为$S$，现在如果强制让第$1,2, \ldots , n$个点能被所有关键点到达，求$\sum \limits_{i \in S} c_i - \sum \limits_{j \in U} w_j$的最小值。$(2 \le n \le 3 \cdot 10^5, n - 1 \le m \le \min(3 \cdot 10^5, \frac{n(n-1)}{2}), 1 \le k \le n)$

首先找到所有边双联通分量将其缩点，可以证明每一个边双都可以给边定向从而形成强连通分量，因此每一个边双内部不用考虑边的定向问题。

现在原图转化为了一棵树，下面所说的关键点指包含关键点的边双。以一个关键点为根，将所有叶子节点为非关键点的点都向上缩，权值进行叠加，因为它们显然定向为上才有意义，因此可以锁到距离最近的关键点，这样可以简化后续讨论。

现在我们所有叶子节点均为关键点，那么能被所有关键点到达的点一定组成一个连通块，连通块内部所有边无向，其它边均被定向。因此我们可以使用树形dp解决下面的问题，设$f_i$为以$i$为根的子树中包含点$i$的连通块的最大权值，转移为$$f_i=C_i+\sum_{{j \in son_i}}\max(f_j-w,0)$$其中$w$为对应的边权，$C_i$为缩点后的总权值，那么单次dp中对于根节点最终所求的答案为$f_{root}$。

我们最后再进行一次换根dp，即可以每个点为根求出最终的答案。注意到因为第一次我们选的关键点为根，所以换根过程中始终满足所有叶子节点均为关键点这一条件。