题解：P12626 [NAC 2025] Most Scenic Cycle

#define maxn 1000005
#define inf 0x3f3f3f3f3f3f3f3f

int n,m,res;

struct node{
	int x;
	node(int xx=-inf){x=xx;}
};
node T(node a,node b){
	res=max(res,a.x+b.x);
	return node(max(a.x,b.x));
}
node C(node a,node b){
	return node(a.x+b.x);
}

map<int,node>G[maxn];
int ord[maxn];
void add(int u,int v,node w){
	if(G[u].count(v)) G[u][v]=G[v][u]=T(G[u][v],w);
	else G[u][v]=G[v][u]=w;
}
void dele(int u,int v){
	G[u].erase(v),G[v].erase(u);
}

void build()
{
	queue<int>q; int idx=0;
	For(i,1,n)if(G[i].size()<=2)q.push(i);
	while(q.size()){
		int u=q.front();q.pop();
		if(ord[u])continue;
		ord[u]=++idx;
		if(G[u].size()==1){
			auto [v,w]=*G[u].begin();
			if(G[v].size()<=2)q.push(v);
		}
		if(G[u].size()==2){
			auto [x,w1]=*G[u].begin();
			auto [y,w2]=*G[u].rbegin();
			dele(u,x),dele(u,y);
			add(x,y,C(w1,w2));
			if(G[x].size()<=2)q.push(x);
			if(G[y].size()<=2)q.push(y);
		}
	}
	assert(idx==n);
}

signed main()
{
	n=read(),m=read();
	res=-inf;
	For(i,1,m){
		int u=read(),v=read(),w=read();
		add(u,v,w);
	}
	build();
	cout<<res;
	return 0;
}
/*
6 5
1 2 9
2 3 9
3 4 9
3 4 -9
4 1 9
*/