基环树
y总的进阶课 基环树dp
首先n个节点n个边，那么就是一个环，然后向其中插入点，就是这个环周围连接几个链。这个板块可以写在dp中，也可以写在图论中不过，在我这里随便了，都可以了属于是。
基环树命名很形象，就是一个一些树基于一个环上。一些题目就会有一个点只有一个出边的性质，那么这样会形成环，但是在一个连通图上只会形成有且只有一个环，就相当于在一个树上加上了一条边增加了一个环。
那么由于有环，那么可以想仙人掌那样进行思考问题，或者就当成普通的图进行考虑问题，当然添加了这个条件当然是可以利用其特殊的性质进行计算。由于除了哪一个环，剩下的都是树，那么我们比如在进行dp的时候对于树上的情况，我们就正常的使用树上的dp进行计算，对于两个树之间的性质，那么我们就要利用这个一个环了。
突破口就在环上。
例题1：P1453 城市环路
题目保证n个点，n条边，整个图连通，然后每个点有一个权值，有边不同同时选两个，那么求出最大的选的点的权值之和。
那么我们一眼就可以看出这个题目以类似二分图上的点覆盖问题，只不过这个图不是一个二分图（有环，那么懂的同学可以直接写一个 带花树 算法，来进行一般图匹配，但是我们这里还是使用基环树，一般的树形dp。
那么先考虑树上的情况，那么类似于==没有上司的舞会==这道题，对于每个点表示选和不选两种状态，来进行状态转移，但是这是一个有环的问题，那么我们可以找到环，然后随便找一个边将环断开，这样就是一个树了，那么我们只需要将断开的边的限制作用考虑进去就行了，即为不能同时选这条边上的两个点。
// https://www.luogu.com.cn/problem/P1453
int n,m ;
int h[N],e[M],ne[M],rm[M],idx ;
int p[N],f1[N][2],f2[N][2] ;
bool ins[N] ;
int ans ;
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;
}
void dfs_f(int u,int z,int fa,int f[][2]){
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(rm[i] || j == fa) continue ;
dfs_f(j,z,u,f) ;
f[u][0] += max(f[j][0],f[j][1]) ; // 当前u没有选
}
f[u][1] = -INF ;
if(u != z){ // 代表可以选择u
f[u][1] = p[u] ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(rm[i] || j == fa) continue ;
f[u][1] += f[j][0] ;
}
}
}
void dfs_c(int u,int from){
ins[u] = 1 ;
for(int i = h[u] ;~ i ; i = ne[i]){
int j = e[i] ;
if(i == (from ^ 1) || rm[i]) continue ; // 如果这个边是来的反向边，或者删除过
if(!ins[j]) dfs_c(j,i) ;
else{
rm[i] = 1 ;
rm[i^1] = 1 ;
dfs_f(j,-1,u,f1) ; // 没有选择j，可以选择u这个点
dfs_f(j,u,u,f2) ; // 选择j，那么就不可以选择u这个点了
ans = max(ans,f1[j][0]) ; // 没有选择j
ans = max(ans,f2[j][1]) ; // 选择了j
}
}
ins[u] = 0 ;
}
int main(){
scanf("%d",&n) ;
for(int i = 0 ; i < n ; i ++ ) scanf("%d",&p[i]) ;
memset(h,-1,sizeof h) ;
for(int i = 0 ; i < n ; i ++){
int a,b ;
scanf("%d%d",&a,&b) ;
add(a,b),add(b,a) ;
}
dfs_c(0,-1) ; // 找环
double tot ;
scanf("%lf",&tot) ;
printf("%.1f\n",ans * tot); // 计算出答案
例题2：[IOI2008] Island
题目说有n个岛，每个岛只有一个桥，那么你现在想要从一个岛出发沿着桥走，但是不走已经走过的桥，一个连通块只能走一次，请问可以走的最长距离是什么？
那么这道题转化为在一个连通块中的最长距离是什么，这对于一个树上的问题来说就是一个简单的dp。但是对于有环的题目来说就不是那么好做了，那么就是说在两个树之间，中间是一个环，那么最长的距离就是$f[i] + f[j] + dis(i,j) \to f[i] + f[j] + sum[j] - sum[i]$将这个式子拆成前缀和的表达形式，那么就可以使用单调队列来进行优化，那么就可以单调队列优化dp，来做到线性，由于又是一个环，所以可以使用环的常用技巧拆开，变成两倍。
// https://www.luogu.com.cn/problem/P4381
using ll = long long ;
const int N = 1e6 + 100 ,M = 2 * N ,INF = 0x3f3f3f3f ;
int n ;
int h[N],w[M],e[M],ne[M],idx ;
int fa[N],fw[N],q[N] ; // 记录这个点是从那个点过来的，就是说记录父节点，和记录父边，找环的时候用的
int cir[N],ed[N],cnt ; // 记录环上的点，，记录环的长度，记录环的个数
ll f[N],s[N],sum[N] ;
bool st[N],ins[N] ; // 第一个st代表是否遍历过，第二个是代表是否在栈中（判断环用的
ll ans ;
void add(int a,int b,int c){
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++ ;
}
void dfs_c(int u,int from){ // 找环，并且记录环上的前缀和
st[u] = ins[u] = 1 ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(i == (from ^ 1)) continue ;
fa[j] = u,fw[j] = w[i] ;
if(!st[j]) dfs_c(j,i) ;
else if(ins[j]){
cnt ++ ;
ed[cnt] = ed[cnt-1] ;
ll sum = w[i] ;
for(int k = u ; k != j ; k = fa[k]){
s[k] = sum ;
sum += fw[k] ;
cir[ ++ ed[cnt]] = k ;
}
cir[++ ed[cnt]] = j,s[j] = sum ;
}
}
ins[u] = 0 ;
}
ll dfs_f(int u,int fa){ // 找到距离这个点最远的点
ll d1 = 0,d2 = 0 ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(j == fa || st[j]) continue ;
ll t = dfs_f(j,u) + w[i] ;
if(t > d1) d2 = d1,d1 = t ;
else if(t > d2) d2 = t ;
}
ans = max(ans,d1 + d2) ; // 更新当前连通块的最长距离答案
return d1 ;
}
int main(){
scanf("%d",&n) ;
memset(h,-1,sizeof h) ;
for(int i = 1 ; i <= n ; i++){
int a,b ;
scanf("%d%d",&a,&b) ;
add(i,a,b),add(a,i,b) ;
}
for(int i = 1 ;i <= n ; i ++)
if(!st[i])
dfs_c(i,-1) ;
memset(st,0,sizeof st) ;
for(int i = 1 ; i <= ed[cnt] ; i ++) st[cir[i]] = 1 ; // 将在环上的点判断出来
ll res = 0 ;
for(int id = 1 ; id <= cnt ; id ++){ // 枚举环
ans = 0 ;
int sz = 0 ;
for(int i = 1,j = ed[id-1] + 1; j <= ed[id] ; i ++,j ++){
sum[i] = s[cir[j]] ;
f[i] = dfs_f(cir[j],-1) ;
sz = i ;
}
for(int i = 1 ; i <= sz ; i ++)
f[i + sz] = f[i],sum[i + sz] = sum[i] + sum[sz] ;
int hh = 0,tt = -1 ;
for(int i = 1 ; i <= 2 * sz ; i ++){ // 单调队列优化处理不同树之间的
while(hh <= tt && q[hh] <= i - sz) hh ++ ;
if(hh <= tt)
ans = max(ans,f[q[hh]] + f[i] + sum[i] - sum[q[hh]]) ;
while(hh <= tt && f[q[tt]] - sum[q[tt]] <= f[i] - sum[i]) tt -- ;
q[++tt] = i ;
}
res += ans ;
}
printf("%lld\n",res) ;
例题3：ACwing 1080. 骑士
与例题1差不多，但是这个会有多个连通图，，注意这个题只能开单向边，开双向边内存会炸。
例题4：ACwing创世纪
题目中说 每个被选的一定要有一个没有被选的点 限制这个点，就是说每个选上的点一定有一个 没有被选上的点指向这个点，那么对于一个树来说，加入儿子指向父节点，那么状态计算就是 父节点没有选，那么儿子中可选可不选，如果父节点选了，那么儿子要有一个不选。
主要想清楚树上的状态转移，然后考虑删去的那条边，如果不利用删去的拿条边，可以之接进行计算，如果利用了，就是说u那个点就不需要儿子不选就可以选。
// https://www.acwing.com/problem/content/361/
int n,m ;
int h[N],e[N],ne[N],rm[N],idx ;
int f1[N][2],f2[N][2],ans ;
bool st[N],ins[N] ;
// 题目中说 每个被选的一定要有一个没有被选的点 限制这个点
// 就是说每个选上的点一定有一个 没有被选上的点指向这个点
// 那么对于一个树来说，加入儿子指向父节点
// 那么状态计算就是 父节点没有选，那么儿子中可选可不选
// 如果父节点选了，那么儿子要有一个不选
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx ++ ;
}
void dfs_f(int u,int z,int f[][2]){
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(rm[i]) continue ; // 边被删除了
dfs_f(j,z,f) ;
f[u][0] += max(f[j][0],f[j][1]) ; // 这个点没有选，所以儿子可选可不选
}
if(u == z) f[u][1] = f[u][0] + 1 ;
else{
f[u][1] = -INF ;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(rm[i]) continue ;
f[u][1] = max(f[u][1],f[u][0] - max(f[j][0],f[j][1]) + f[j][0] + 1 ) ;
}
}
}
void dfs_c(int u){
st[u] = ins[u] = 1;
for(int i = h[u] ; ~ i ; i = ne[i]){
int j = e[i] ;
if(!st[j]) dfs_c(j) ;
else if(ins[j]){
rm[i] = 1 ; // 将 u -> j的边断开，所以只后就是一个树了，根是j
dfs_f(j,-1,f1) ; // 第二个参数代表不能选择那个点
dfs_f(j,u,f2) ;
ans += max(max(f1[j][0],f1[j][1]),f2[j][0]) ;
}
}
ins[u] = 0 ;
}
int main(){
scanf("%d",&n) ;
memset(h,-1,sizeof h) ;
for(int i = 1; i <= n ; i ++){
int b;
scanf("%d",&b) ;
add(b,i) ; // 反向边
}
for(int i = 1 ; i <= n ; i ++)
if(!st[i])
dfs_c(i) ;
printf("%d\n",ans) ;
