（严格）次小生成树

介绍

次小生成树顾名思义就是比最小生成树大一点的生成树，严谨地说就是把一张图所有的生成树都找出来并按照边权和从小到大排序，从头开始第一个比最小生成树边权更大的生成树就是次小生成树

实现

不难想到最小生成树和次小生成树的边应该有很多都是一样的，只有部分边有所不同

那么我们就有这样一种想法，首先找出一个最小生成树，在这棵最小生成树的基础上进行修改

具体地说就是在非最小生成树上边中按照边权从小到大枚举每一条边，把枚举到的边加入最小生成树中，这时最小生成树上会出现一个环，我们把这个环上的最大边断开就可以得到非严格最小生成树了（证明是什么？能吃吗？）

如何在环上找最大值呢？可以发现添加的边所连接的两个节点到他们在最小生成树上的LCA的两条路径就会组成一个环，我们需要的就是这两条路径上的最大边权，寻找边权可以在利用倍增求LCA时顺便维护

此外由于我们需要找的是严格次小生成树，所以如果环上的最大边边权恰好等于我们新加入的边的边权，我们就需要删去环上边权第二大的边，在倍增时也需要同时维护，维护次大边权有点细节，具体的内容代码里有详细注释

Code

板子传送门（Luogu P4180）

#include
#define in read()
using namespace std;
typedef long long ll;
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
char B[1<<15],*S=B,*T=B;
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<48)c=getchar();
    while(c>47)x=(x*10)+(c^48),c=getchar();
    return x;
}
inline void mwrite(ll a)
{
    if(a>9)mwrite(a/10);
    putchar((a%10)|48);
}
inline void write(ll a,char c)
{
	mwrite(a);
	putchar(c);
}
#define MAXN 100005
#define MAXM 300005
#define INF 0x7f7f7f7f7f7f7f7f
struct Edge_all//原图边 
{
	int fr,to,w;
	bool isin;
	Edge_all(int Fr=0,int To=0,int W=0):isin(0),fr(Fr),to(To),w(W){}
	bool operator <(const Edge_all& x) const{return wmx[f[pos][i-1]][i-1])
		{//前半段最大值更大就继承前半段更大值，次大值取前半段的次大值和后半段的最大值中更大的 
			mx[pos][i]=mx[pos][i-1];
			mx2[pos][i]=max(mx2[pos][i-1],mx[f[pos][i-1]][i-1]);
		}
		else if(mx[pos][i-1]-1;--i)
		if(dep[x]-(1<=dep[y])
			x=f[x][i];
	if(x==y) return x;
	for(int i=18;i>-1;--i)
		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline ll solve(int x,int y,int w)
{
	int l=lca(x,y),maxn=0,maxn2=0;
	for(int i=18;i>-1;--i)
	{
		if(dep[f[x][i]]>=dep[l])//还没跳到lca就把答案更新 
		{
			if(maxn==mx[x][i]) maxn2=max(mx2[x][i],maxn2);
			//最大值一样就更新次大值
			if(maxn>mx[x][i]) maxn2=max(mx[x][i],maxn2);
			//最大值无法更新就和次大值比较
			if(maxn=dep[l])
		{
			if(maxn==mx[y][i]) maxn2=max(mx2[y][i],maxn2);
			if(maxn>mx[y][i]) maxn2=max(mx[y][i],maxn2);
			if(maxn