基环树由普通树额外增加一条边组成，是图论经典问题之一。
给定一个有向图(不保证连通)，每个点有一条出边。问有多少种方案能将边重定向，使得图中不存在有向环。
首先不难得出结论每个点一条出边的图正好构成基环树森林。
单独考虑每棵基环树，发现只要基环树上的环上所有边不同向即可，其余边方向任意。设第 $i$ 个基环树的环长度为 $w_i$，则答案为
$$ 2^{n-\sum w_i}\prod (2^{w_i}-2) $$
给定 $n$ 个物品，每个物品有一个权值 $w_i$，同时第 $i$ 个物品不能和第 $p_i$ 个物品同时选择。问能得到的最大权值。
问题等价于基环树森林的最大权独立集。
考虑每个基环树，任取环上的一条边，记为 $(u,v)$。删除这条边，然后跑强制不取 $u$ 情况下的最大权独立集和强制不取 $v$ 情况下的最大权独立集。
于是每个基环树的贡献为上述两种情况下的最大者，可以通过树形 $\text{dp}$ 计算，最后答案为所有基环树贡献相加。
关于找 $(u,v)$ 边可以通过并查集，而强制不取可以将点权设为 $-\text{inf}$ 或者将不取的点为根节点进行 $\text{dp}$。
题目大意就省略了，大概就是给定基环树森林，求所有基环树的最长路径之和。(注意最长路径 $\neq$ 直径)
考虑每棵基环树的情况，首先找到环，先不考虑环上的边，求出环上每个点的子树的直径的最大值，这是可能的答案之一。
另外求出环上每个点到它子树的叶子节点的最远距离 $d$。设环长为 $s$，任取环上的点对 $(u,v)$，于是另一种答案为
$$ \max(d(u)+d(v)+\text{dis}(u,v),d(u)+d(v)+s-\text{dis}(u,v)) $$
考虑规定一个环上的起始点，于是 $\text{dis}(u,v)=\text{pre}(u)-\text{pre}(v)$，维护两个前缀 $\text{max}$ 即可 $O(n)$ 统计所有点对贡献。
给定一个基环树，要求在图上找到一个点，使得该点到其他点的最大距离最小。(该点可以在边上的某个位置)
显然答案是基环树的直径除以 $2$，至于基环树的直径，首先子树贡献同基环树的最长路径，但环上点对 $(u,v)$ 的贡献改为
$$ \min(d(u)+d(v)+\text{dis}(u,v),d(u)+d(v)+s-\text{dis}(u,v)) $$
考虑依次断开一条边，得到链后计算 $\max(d(u)+d(v)+\text{dis}(u,v))$ 得到生成树的直径，则所有断边情况中的最小值就是基环树的直径。
简短证明一下上述结论：首先任意断开一条环上的边可以得到一棵生成树，显然生成树的直径不小于基环树的直径。
事实上，取基环树直径的中点 $rt$，做 $rt$ 的最短路生成树，则最短路生成树的直径等于基环树的直径。证毕。
但这样时间复杂度是 $O(n^2)$，考虑优化。记环上的点分别为 $u_1,u_2\cdots u_m$，考虑先断开 $(u_1,u_m)$ 边，求出前缀
$$ \text{pre1}(i)=\max_{1\le j\le i}(d(u_j)+\text{dis}(u_j,u_1))\\ \text{pre2}(i)=\max_{1\le j,k\le i}(d(u_j)+d(u_k)+\text{dis}(u_j,u_k)) $$
类似定义后缀 $\text{suf1}(i),\text{suf2}(i)$，于是断开 $(u_1,u_m)$ 边的贡献为 $\text{pre2}(k)$。
接下来考虑断开 $(u_i,u_{i-1})$ 的边，分 $(u\lt i,v\ge i),(u,v\lt i),(u,v\ge i)$ 三种情况讨论，此时贡献为
$$ \max\left(\text{pre1}(i-1)+\text{suf1}(i)+\text{dis}(u_{i-1},u_i),\max(\text{pre2}(i-1),\text{suf2}(i))\right) $$
总时间复杂度 $O(n)$。