题目链接：
http://172.16.0.132/senior/#main/show/5905
题目：
oi_juruo热爱一款名叫黑暗之魂的游戏。在这个游戏中玩家要操纵一名有 点生命值的无火的余灰在一张地图中探险。地图中有$n$个篝火（也就是存档点）。在篝火处休息可以将生命值恢复满。每个篝火都会向其他篝火的其中之一连有一条通道（显然，通道是双向的），这些篝火之间都相互可达。也就是说，这是一张$n$个点，$n$条边的无向连通图。每条通道里都有一些怪物，经过oi_juruo的分析，他得到了每条边的怪物会对他造成的伤害值 .为了向oier们表演他高超的游戏技巧，他要从任意一个篝火跑到任意另一个篝火而不在之间的篝火休息，在此期间，他会和他经过的通道中的怪物战斗并损失 的生命值。现在oi_juruo想知道，他的生命值 至少为多少，才能完成任意一条旅途。oi_juruo并不傻，他会走最安全的路。本题时限为3000ms
题目大意：
给出一棵基环树，定义任意两点之间的距离为两点之间的最短路径，最大距离为多少
题解：
分别考虑环上的每一个点
显然我们首先要找到环，考虑用类似拓扑排序的做法，即每次找度数为1的叶子节点不断向上更新，最后环上的点的度数一定为2
$f[x]$表示以$x$为根的子树中的直径，可以在拓扑排序的过程中处理出
我们已知以环上每一个点为根节点的子树的直径，问题转化成了给出一个环，环上的每一个点有一个点权，点与点之间有边权，设$dis[i][j]$为环上两点$i,j$的距离（最短路径），要计算最大的$f[i]+f[j]+dis[i][j]$
由于只能走最短路径，显然$dis[i]][j]$小于等于环的周长$S$的二分之一。我们断环成链，在可行区间范围内维护单调队列。
具体实现是令$a[i]$为节点$i$的点权，$b[i]$为链开头到节点i的路径前缀和，对于每个$i$，答案就是$a[i]+a[j]+b[i]-b[j](b[i]-b[j]<=frac{S}{2})$取最大值，显然满足决策单调性
#include<algorithm> #include<cstring> #include<cstdio> #include<iostream> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N=1e6+15; int n,tot; ll ans; int head[N],in[N],tmp[N],qq[N]; ll f[N],dis[N],b[N],a[N]; struct EDGE { int to,nxt; ll w; }edge[N<<1]; inline ll read() { char ch=getchar(); ll s=0,f=1; while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return s*f; } void add(int u,int v,ll w) { edge[++tot]=(EDGE){v,head[u],w}; head[u]=tot; } void topsort() { queue<int> q; for (int i=1;i<=n;i++) if (in[i]==1) q.push(i); while (!q.empty()) { int k=q.front();q.pop(); for (int i=head[k];i;i=edge[i].nxt) { int y=edge[i].to; if (in[y]==1) continue; ans=max(ans,f[k]+f[y]+edge[i].w); f[y]=max(f[y],f[k]+edge[i].w); if ((--in[y])==1) q.push(y); } } } void dp(int x) { int t=0,y=x,pp; ll len,S=0; do { a[++t]=f[y]; tmp[y]=1; for(pp=head[y];pp;pp=edge[pp].nxt) if(!tmp[edge[pp].to]&&in[edge[pp].to]==2) { y=edge[pp].to; b[t+1]=b[t]+edge[pp].w; break; } }while(pp); if (t==1) return; if (t==2) { for (int i=head[y];i;i=edge[i].nxt) { if (edge[i].to==x) {len=edge[i].w;break;} } ans=max(ans,f[x]+f[y]+len); return; } for (int i=head[y];i;i=edge[i].nxt) { if (edge[i].to==x) { S=b[t]+edge[i].w; b[t+1]=b[t]+edge[i].w; } } for (int i=1;i<t;i++) a[i+t]=a[i],b[t+i]=b[t+1]+b[i]; int l=1,r=1; qq[l]=1; for (int i=2;i<2*t;i++) { while (l<=r&&(b[i]-b[qq[l]]>S/2||i-qq[l]>=t)) l++; if (l<=r) ans=max(ans,b[i]-b[qq[l]]+a[qq[l]]+a[i]); while (l<=r&&a[qq[r]]-b[qq[r]]<=a[i]-b[i]) r--; qq[++r]=i; } } int main() { freopen("darksoul.in","r",stdin); freopen("darksoul.out","w",stdout); n=read(); for (int i=1,u,v,w;i<=n;i++) { u=read();v=read();w=read(); in[u]++;in[v]++; if (u==v) continue; add(u,v,w);add(v,u,w); } topsort(); for (int i=1;i<=n;i++) { if (in[i]==2) { dp(i); break; } } printf("%lld ",ans+1); return 0; }