题目链接：传送门
之所以评黑，是因为实在是太难调了。（又回调了）。
对于有 $40%$ 的数据，$n\le 3000$，这部分我们可以暴力删边，然后暴力求直径即可。
那么对于 $100%$ 的数据：
首先如果删的两条边都是环上的边，这个比较好做，可以用线段树维护环，将环断链并翻两倍然后用线段维护。
线段树维护的信息有，延伸到区间左端点和右端点最长的链，记为 $lnum,rnum$，即区间内的最长直径，即为 $maxn$。
建树时的三个信息即为从环上节点到自己子树最长的距离作为延伸到区间左端点和右端点最长的链，以环上节点为根的子树的直径，第一个可以 $\text{dfs}$ 解决，第二个可以树形 $\text{dp}$ 解决。
合并线段树两个区间 $(ls,rs)$，新区间的左端点，即为左区间的 $lnum$ 与右区间的 $lnum$ 加上右区间的左端点到左区间的左端点的距离的最大值，即 $\max(ls_{lnum},rs_{lnum}+dis_{mid+1}-dis_l,)$，右区间同理，而两区间合并 $maxn$，即为两边的 $maxn$ 或是两区间合并起来的答案，即为 $\max(ls_{maxn},rs_{maxn},ls_{rnum}+rs_{lnum}+dis_{mid+1}-dis_{mid})$。
最后断两条环上边求最大值，就用线段树求区间的 $maxn$ 即可，具体实现可以看代码。
然后就是删一条环与一条非环边。
那我对于删一条非环边，就要修改其线段树的信息。
首先是 $lnum,rnum$，我们可以提前预处理出来原来的链上每一个点出发到子树的次长链，记 $i$ 点的次长链（这里的次长链不会与最长链有任何公共部分）加上到达对应环上节点的距离为 $g_i$，这个可以用之前 $\text{dp}$ 求解的值来求解，删除一条这个链上的边就可以往上找最大的 $g_i$，这个可以从上往下求前缀最大值预处理即可。
然后是 $maxn$，这个很难搞，如果直径的一条边被截，那么新子树的直径的端点一定有一个是原直径没被截的端点上。
考虑证明，如果带直径 $(l_1,r_1),(l_2,r_2)$ 的两棵树合并，直径的可能性就只有六种，即为 $(l_1,r_1,l_2,r_2)$ 中选两个数来组合。
反过来同理，若有两个端点 $(l_1,r_1)$ 的直径，那么 $l_1,r_1$ 一定是被分裂后两棵子树的直径的端点。
所以我们实际上只需要求断一条边后没有被断掉的直径端点最远能走到的地方。
那么可以预处理出来原直径上每个点能走到的次长的地方（这里次长的地方不会与最长的地方所走的链不会有任何公共部分），这个可以用搜索预处理，然后再从前往后求一个前缀最大值即可。
然后单点修改后根据断环的边求区间最大值就没了。
时间复杂度：$O(n)$
代码及其复杂，建议看懂思路即可，或是打一下删两条环上的边的特殊点。
#include<iostream>
#include<cstdio>
#include<map>
#include<stack>
#define int long long
using namespace std;
const int N=6e5+5;
const int mod=1e9+7;
const int M=25;
int n,cnt,h[N],x1,y1,x2,y2,maxn,num,vis[N],dfn[N],low[N],ins[N],tim,huan[N],dp[N][2],fath[N],too[N][2],depdis[N];
int huhead,hutail,id[N],cnt_huan,dis[2*N],disf[2*N],vishuan[2*N],fid[N],maxzj[N],dep[N],g[N],t[N][25],spd[N][2];
struct segmentree
{
struct node2
{
int lnum,rnum,maxn;
}f[8*N];
inline int ls(int x)
{
return x<<1;
}
inline int rs(int x)
{
return x<<1|1;
}
inline void pushup(int x,int l,int r)
{
int mid=(l+r)>>1;
f[x].lnum=max(f[rs(x)].lnum+dis[mid+1]-dis[l],f[ls(x)].lnum);
f[x].rnum=max(f[ls(x)].rnum+dis[r]-dis[mid],f[rs(x)].rnum);
f[x].maxn=max(f[ls(x)].rnum+f[rs(x)].lnum+dis[mid+1]-dis[mid],max(f[ls(x)].maxn,f[rs(x)].maxn));
}
void build(int x,int l,int r)
{
if(l==r)
{
f[x]={dp[fid[l]][0],dp[fid[l]][0],maxzj[fid[l]]};
//cout<<l<<" "<<fid[l]<<" asdf"<<f[x].maxn<<" "<<cnt_huan<<endl;
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x,l,r);
}
void update(int x,int l,int r,int nl,int k1,int k2)
{
if(l==r)
{
f[x]={k1,k1,k2};
return;
}
int mid=(l+r)>>1;
if(mid>=nl)update(ls(x),l,mid,nl,k1,k2);
else update(rs(x),mid+1,r,nl,k1,k2);
pushup(x,l,r);
}
node2 search(int x,int l,int r,int nl,int nr)
{
//cout<<x<<" "<<l<<" "<<r<<" "<<nl<<" "<<nr<<" "<<f[x].maxn<<endl;
if(l>=nl&&r<=nr)return f[x];
int mid=(l+r)>>1;
if(mid>=nl&&mid<nr)
{
node2 lc=search(ls(x),l,mid,nl,nr),rc=search(rs(x),mid+1,r,nl,nr);
//cout<<dis[mid+1]-dis[mid]<<"safasdf\n";
return {max(lc.lnum,rc.lnum+dis[mid+1]-dis[l]),
max(rc.rnum,lc.rnum+dis[r]-dis[mid]),
max(max(lc.maxn,rc.maxn),lc.rnum+rc.lnum+dis[mid+1]-dis[mid])};
}
else if(mid>=nl)return search(ls(x),l,mid,nl,nr);
else return search(rs(x),mid+1,r,nl,nr);
}
}t1;
struct node
{
int to,data,next;
}a[2*N];
inline void addedge(int u,int v,int w)
{
a[++cnt]={v,w,h[u]};
h[u]=cnt;
}
stack<int>s;
void Tarjan(int x,int fa)
{
dfn[x]=low[x]=++tim;
ins[x]=1;
s.push(x);
for(int i=h[x];i!=0;i=a[i].next)
{
int v=a[i].to;
if(v==fa)continue;
if(!dfn[v])Tarjan(v,x),low[x]=min(low[x],low[v]);
else if(ins[v])low[x]=min(dfn[v],low[x]);
}
if(low[x]==dfn[x])
{
bool flag=0;
while(s.top()!=x)
{
flag=1;
ins[s.top()]=0;
huan[s.top()]=1;
s.pop();
}
ins[s.top()]=0;
if(flag)huan[s.top()]=1;
s.pop();
}
}
void findzj(int hua,int x,int fa,int deep)
{
depdis[x]=deep;
dep[x]=dep[fa]+1;
t[x][0]=fa;
for(int i=1;i<=20;i++)t[x][i]=t[t[x][i-1]][i-1];
fath[x]=hua;
dp[x][0]=0;
dp[x][1]=0;
int t1=x,t2=x;
too[x][0]=x;
int li=0;
for(int i=h[x];i!=0;i=a[i].next)
{
int v=a[i].to;
if(v==fa||huan[v])continue;
findzj(hua,a[i].to,x,deep+a[i].data);
if(dp[v][0]+a[i].data>dp[x][1])dp[x][1]=dp[v][0]+a[i].data,t2=too[v][0];
if(dp[x][1]>dp[x][0])swap(dp[x][1],dp[x][0]),swap(t1,t2);
if(maxzj[v]>maxzj[x])li=v,maxzj[x]=maxzj[v];
}
if(dp[x][0]+dp[x][1]>=maxzj[x])maxzj[x]=dp[x][1]+dp[x][0],too[x][0]=t1,too[x][1]=t2;
else too[x][0]=too[li][0],too[x][1]=too[li][1];
g[x]=deep+dp[x][1];
}
void gethsdis(int x,int fa)
{
vishuan[x]=1;
id[x]=++cnt_huan;
fid[cnt_huan]=x;
hutail=x;
for(int i=h[x];i!=0;i=a[i].next)
{
int v=a[i].to;
if(v==fa||!huan[v])continue;
disf[cnt_huan]=a[i].data;
if(vishuan[v])continue;
dis[cnt_huan+1]=dis[cnt_huan]+a[i].data;
gethsdis(v,x);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)if(dep[t[x][i]]>=dep[y])x=t[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)if(t[x][i]!=t[y][i])x=t[x][i],y=t[y][i];
return t[x][0];
}
int lasdis(int x,int fa,int idt,int deep)
{
//cout<<x<<" "<<fa<<" "<<idt<<" "<<deep<<" "<<too[fath[x]][0]<<" "<<too[fath[x]][1]<<endl;
int result=deep;
for(int i=h[x];i!=0;i=a[i].next)
{
int v=a[i].to;
if(v==fa||(huan[v]&&v!=fath[x]))continue;
int numt=lasdis(v,x,idt,deep+a[i].data);
if((dep[v]>=dep[lca(too[fath[x]][0],too[fath[x]][1])]||dep[x]>=dep[lca(too[fath[x]][0],too[fath[x]][1])])&&((lca(x,too[fath[x]][idt^1])==x&&lca(v,too[fath[x]][idt^1])==v)||(lca(x,too[fath[x]][idt])==x&&lca(v,too[fath[x]][idt])==v)))continue;
result=max(result,numt);
}
return spd[x][idt]=result;
}
void predis(int x,int fa,int idt)
{
spd[x][idt]=max(spd[x][idt],spd[fa][idt]);
for(int i=h[x];i!=0;i=a[i].next)
{
int v=a[i].to;
if(v==fa||(huan[v]&&v!=fath[x]))continue;
predis(a[i].to,x,idt);
}
}
void findvis(int x,int fa)
{
vis[x]=1;
for(int i=h[x];i!=0;i=a[i].next)
{
int v=a[i].to;
if(v==fa||huan[v])continue;
if(dp[x][0]==dp[v][0]+a[i].data)findvis(v,x);
}
}
void findg(int x,int fa)
{
g[x]=max(g[fa],g[x]);
for(int i=h[x];i!=0;i=a[i].next)
{
int v=a[i].to;
if(v==fa||huan[v])continue;
findg(v,x);
}
}
inline int read()
{
char ch=getchar();
int sum=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
return sum;
}
void write(int x)
{
if(x<0)
{
x=-x;
putchar('-');
}
if(x/10)write(x/10);
putchar(x%10+48);
}
signed main()
{
freopen("konjac.in","r",stdin);
freopen("konjac.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
int u,v,w;
u=read(),v=read(),w=read();
addedge(u,v,w);
addedge(v,u,w);
}
Tarjan(1,0);
for(int i=1;i<=n;i++)if(huan[i])findzj(i,i,0,0);
for(int i=1;i<=n;i++)
{
if(huan[i])
{
huhead=i;
gethsdis(i,0);
for(int i=cnt_huan+1;i<=2*cnt_huan;i++)dis[i]=dis[i-1]+disf[(i-2)%cnt_huan+1],fid[i]=fid[i-cnt_huan];
break;
}
}
for(int i=1;i<=cnt_huan;i++)
{
lasdis(too[fid[i]][0],0,0,0);
lasdis(too[fid[i]][1],0,1,0);
predis(too[fid[i]][0],0,0);
predis(too[fid[i]][1],0,1);
findvis(fid[i],0);
findg(fid[i],0);
}
t1.build(1,1,cnt_huan*2);
int q;
q=read();
for(int i=1;i<=q;i++)
{
x1=read(),y1=read(),x2=read(),y2=read();
if(id[x1]&&id[x2]&&id[y1]&&id[y2])
{
x1=id[x1],y1=id[y1],x2=id[x2],y2=id[y2];
if(x1>y1)swap(x1,y1);
if(x2>y2)swap(x2,y2);
if(x1>x2||((x1==x2)&&(y1<y2)))swap(x1,x2),swap(y1,y2);
if(x1==1&&y1==cnt_huan)x1+=cnt_huan,swap(x1,y1),swap(x1,x2),swap(y1,y2);
double ans=(t1.search(1,1,cnt_huan*2,y1,x2).maxn+t1.search(1,1,cnt_huan*2,y2,x1+cnt_huan).maxn)/2.0;
printf("%.1lf\n",ans);
}
else
{
if(id[x2]&&id[y2])swap(x1,x2),swap(y1,y2);
if(id[x1]>id[y1])swap(x1,y1);
if(dep[x2]>dep[y2])swap(x2,y2);
double ans=maxzj[y2]/2.0;
int num1=dp[fath[x2]][0];
if(vis[x2]&&vis[y2])
{
t1.update(1,1,cnt_huan*2,id[fath[x2]],g[x2],maxzj[fath[x2]]);
t1.update(1,1,cnt_huan*2,id[fath[x2]]+cnt_huan,g[x2],maxzj[fath[x2]]);
num1=g[x2];
}
bool flag1=(lca(x2,too[fath[x2]][0])==x2&&lca(y2,too[fath[x2]][0])==y2&&dep[x2]>=dep[lca(too[fath[x2]][0],too[fath[x2]][1])]);
bool flag2=(lca(x2,too[fath[x2]][1])==x2&&lca(y2,too[fath[x2]][1])==y2&&dep[x2]>=dep[lca(too[fath[x2]][0],too[fath[x2]][1])]);
if(flag1||flag2)
{
int num2=0;
if(flag1)num2=spd[x2][1];
if(flag2)num2=spd[x2][0];
t1.update(1,1,cnt_huan*2,id[fath[x2]],num1,num2);
t1.update(1,1,cnt_huan*2,id[fath[x2]]+cnt_huan,num1,num2);
}
x1=id[x1],y1=id[y1];
if(x1==1&&y1==cnt_huan)x1=cnt_huan,y1=cnt_huan+1;
ans+=t1.search(1,1,cnt_huan*2,y1,x1+cnt_huan).maxn/2.0;
printf("%.1lf\n",ans);
t1.update(1,1,cnt_huan*2,id[fath[x2]],dp[fath[x2]][0],maxzj[fath[x2]]);
t1.update(1,1,cnt_huan*2,id[fath[x2]]+cnt_huan,dp[fath[x2]][0],maxzj[fath[x2]]);
}
}
return 0;
}
/*
8
3 4 10
2 1 2
3 1 10
4 1 1
5 2 5
6 5 2
7 4 3
8 4 6
3
1 4 3 4
1 4 1 3
1 3 3 4
8
3 4 10
2 1 2
3 1 10
4 1 1
5 2 5
6 5 2
7 4 3
8 4 6
3
4 1 5 2
3 1 7 4
4 1 3 1
*/