基环树直径裸题
分别在子树做DP，环上做DP，环上可以用单调队列优化到\(O(n)\)
写起来很麻烦
#include<algorithm>
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
inline int rd(){
int ret=0,f=1;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
while(isdigit(c))ret=ret*10+c-'0',c=getchar();
return ret*f;
}
#define pc putchar
#define space() pc(' ')
#define nextline() pc('\n')
void pot(int x){if(!x)return;pot(x/10);pc('0'+x%10);}
void out(int x){if(!x)pc('0');if(x<0)pc('-'),x=-x;pot(x);}
const int MOD = 1e9+7;
inline void upmax(int &x,int y){x=max(x,y);}
inline void upmin(int &x,int y){x=min(x,y);}
int add(int x,int y){return x+y>MOD?x+y-MOD:x+y;}
int sub(int x,int y){return x-y<0?x-y+MOD:x-y;}
int mul(int x,int y){return (long long)(1ll*x*y)%MOD;}
void Add(int &x,int y){x=add(x,y);}
void Sub(int &x,int y){x=sub(x,y);}
void Mul(int &x,int y){x=mul(x,y);}
const int MAXN = 1000005;
const int M = MAXN<<1;
int n;
int nex[M],to[M],wi[M];
int head[MAXN],ecnt=1;
inline void adde(int x,int y,int w){
nex[++ecnt] = head[x];
to[ecnt] = y;
wi[ecnt] = w;
head[x] = ecnt;
}
int cir[MAXN],vis[MAXN],lenc;
int dfn[MAXN],low[MAXN],tim;
int sta[MAXN],ins[MAXN],top;
void tarjan(int x,int frm){
dfn[x]=low[x]=++tim;
ins[sta[++top]=x]=1;
for(int i=head[x];i;i=nex[i]){
if(i==(frm^1)||i==frm)continue;
int v=to[i];
if(!dfn[v]){
tarjan(v,i);
upmin(low[x],low[v]);
}else if(ins[v]){
upmin(low[x],dfn[v]);
}
}
if(dfn[x]!=low[x]) return;
if(lenc>2) return;
int elm;
do{
elm=sta[top--];
ins[elm]=0;
cir[++lenc]=elm;
}while(elm!=x);
if(lenc<=2) lenc=0;
}
int ans;
int f[MAXN],g[MAXN],h[MAXN];
void dfs(int x,int pre){
for(int i=head[x];i;i=nex[i]){
int v=to[i];
if(v==pre||vis[v]) continue;
dfs(v,x);
upmax(ans,f[x]+f[v]+wi[i]);
upmax(f[x],f[v]+wi[i]);
}
}
int dis[MAXN];
void dfs2(int x){
for(int i=head[cir[x]];i;i=nex[i]){
int v=to[i];
if(v!=cir[x+1])continue;
dis[x]=wi[i];
dfs2(x+1);
}
}
void gfs(int x,int pre){
// vis[x]=1;
for(int i=head[x];i;i=nex[i]){
int v=to[i];
if(v==pre) continue;
gfs(v,x);
upmax(ans,f[x]+f[v]+wi[i]);
upmax(f[x],f[v]+wi[i]);
}
}
int q[MAXN*2],hd=1,tl;
signed main(){
freopen("darksoul8.in","r",stdin);
freopen("darksoul.out","w",stdout);
n=rd();
int x,y,w;
for(int i=1;i<=n;i++){
x=rd();y=rd();w=rd();
if(x==y) continue;
adde(x,y,w);adde(y,x,w);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
for(int i=1;i<=lenc;i++) vis[cir[i]]=1;
for(int i=1;i<=lenc;i++) dfs(cir[i],0);
cir[lenc+1]=cir[1];
dfs2(1);
for(int i=1;i<=lenc;i++) g[i]=g[i+lenc]=f[cir[i]],dis[i+lenc]=dis[i];
dis[0]=dis[lenc]; dis[2*lenc+1]=dis[1];
int sumc=0;
for(int i=1;i<=lenc;i++) sumc+=dis[i];
for(int i=1;i<=lenc*2;i++) dis[i]+=dis[i-1];
int j=1;
while(dis[lenc]-dis[j-1]>sumc/2) j++;
for(int k=j;k<=lenc;k++){
while(hd<=tl&&g[q[tl]]-dis[q[tl]-1]<=g[k]-dis[k-1]) tl--;
q[++tl]=k;
}
for(int i=lenc+1;i<=lenc*2;i++){
while(hd<=tl&&dis[i-1]-dis[q[hd]-1]>sumc/2) hd++;
h[i]=g[q[hd]]-dis[q[hd]-1]+g[i]+dis[i-1];
while(hd<=tl&&g[q[tl]]-dis[q[tl]-1]<=g[i]-dis[i-1]) tl--;
q[++tl]=i;
}
for(int i=lenc+1;i<=lenc*2;i++) upmax(ans,h[i]);
out(ans+1);
return 0;
}