(APIO) 非法捕鱼

…

…

不要问我发生了什么…
要问就去这篇博客下面留言，拷问这个博主的良心
于是！我今天来做这道题了…
（我也是够会作的…)

题目描述

众所周知，是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安全，烟花被安置在远离开关的位置上，通过一些导火索与开关相连。导火索的连接方式形成一棵树，烟花是树叶，如图所示。火花从开关出发，沿导火索移动。每当火花抵达一个分叉点时，它会扩散到与之相连的所有导火索，继续燃烧。导火索燃烧的速度是一个固定常数。图中展示了六枚烟花 的连线布局，以及每根导火索的长度。图中还标注了当在时刻 00 从开关点燃火花时，每一发烟花的爆炸时间。

Hyunmin 为烟花表演设计了导火索的连线布局。不幸的是，在他设计的布局中，烟花不一定同时爆炸。我们希望修改一些导火索的长度，让所有烟花在同一时刻爆炸。例如，为了让图中的所有烟花在时刻 1313 爆炸，我们可以像下图中左边那样调整导火索长度。类似地，为了让图中的所有烟花在时刻 1414 爆炸，我们可以像下图中右边那样调整长度。

修改导火索长度的代价等于修改前后长度之差的绝对值。例如，将上面那副图中布局修改为下面那副图的左边布局的总代价为 66，而修改为右边布局的总代价为 55。

导火索的长度可以被减为 00，同时保持连通性不变。

给定一个导火索的连线布局，你需要编写一个程序，去调整导火索长度，让所有的烟花在同一时刻爆炸，并使得代价最小。

输出：调整导火索长度，让所有烟花同时爆炸，所需要的最小代价。
输入输出样例
输入 #1
7 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
0 0
输出 #1
3
输入 #2
6 26
1 2 66
2 3 11
3 4 73
2 5 77
3 6 33
10 47
1 2 86
2 3 69
3 4 41
4 5 26
5 6 41
2 7 73
3 8 77
4 9 2
5 10 65
0 0
Tip:一共有 20 个测试点。编号为 1 ∼ 20。每个测试点为 5 分。

保证在任一测试点中，数据的组数不会超过 15，且所有数据的 N 之和不超过数据范围中标明的 N 的最大值的 5 倍。

保证所有的输入数据均为不超过 2^31 − 1 的非负整数，保证 N ≥ 1。

保证数据合法。
这道题其实我不大会的说…

question
题目就是说给你一棵树和一条边，然后你可以用这条边连接树上两个节点，求连接之后树上任意两个点的最短路中的 最大值是多少

要求连入边后令求这个最大值最小化，并输出这个最小值

noteskey
先考虑答案最大为树的直径，那么我们发现这条边必然是加在树的直径上的

如果说不加在直径上，那么这个方案一定不是最优的，假设这条边的一个点在树上，另外一个点不在树上，那么把另一个点向直径靠近，答案不会变劣

所以我们先别管树的直径有多少条，肯定是先要找出一条来的

那么我们两边深搜可以求出树的直径，并且沿路记录下直径上的点

然后我们吧直径上的点单独拎出来处理信息，然后根据答案的单调性，二分答案 check 得到解

判断一个解是否合法 具体如下：

令 pre[i] 表示直径起始点到 i 号点的距离， down[i] 表示 i 号点到其子树（不含直径）内点的最长距离

现在我们在直径上加了一条边，那么从一个点到另一个点如果经过直径，那么就会有两条可行路径，于是我们只要康康 直径上任意两点 i、j (i>j)的子树内最远的点之间的距离，是否都能够通过两种路径中的任意一条，使得路径长度小于 mid 就行了：

即，对于直径上任意两点 i,j(i<j)i,j(i<j)，有下列两式任意一式成立则答案可行

down[i]+down[j]+pre[i]-pre[j]<=middown[i]+down[j]+pre[i]−pre[j]<=mid
down[i]+down[j]+|pre[i]-pre[a]|-|pre[j]-pre[b]|+L<=middown[i]+down[j]+∣pre[i]−pre[a]∣−∣pre[j]−pre[b]∣+L<=mid
其中 a,b(a<b)a,b(a<b) 表示用 L 连接的两个点， 且 aa、bb 在所有式子中必须一致

此外，上面的第二个式子可以修改成 4 个不带绝对值的式子，当存在 a、b 满足所有的 4 个式子时原式成立：

limit1=down[i]+pre[i]+down[j]+pre[j]+L-mid
limit1=down[i]+pre[i]+down[j]+pre[j]+L−mid
limit2=down[i]+pre[i]+down[j]-pre[j]+L-mid
limit2=down[i]+pre[i]+down[j]−pre[j]+L−mid
limit3=down[i]-pre[i]+down[j]+pre[j]+L-mid
limit3=down[i]−pre[i]+down[j]+pre[j]+L−mid
limit1=down[i]-pre[i]+down[j]-pre[j]+L-mid
limit1=down[i]−pre[i]+down[j]−pre[j]+L−mid
然后我们就是要找是否存在 a、b 满足：

-pre[a]-pre[b] \le limit1
−pre[a]−pre[b]≤limit1
-pre[a]+pre[b] \le limit2
−pre[a]+pre[b]≤limit2
pre[a]-pre[b] \le limit3
pre[a]−pre[b]≤limit3
pre[a]+pre[b] \le limit4
pre[a]+pre[b]≤limit4
如果存在，那么 mid 就是可行解了

然后我们发现上面式子中都满足出现的 down 和 pre 一一对应，且中间的符号不是 + 就是 -

那么我们对于一个点 i 记录两个值：

down[i]+pre[i]+down[i]-pre[i]
down[i]+down[j]+∣pre[i]−pre[a]∣−∣pre[j]−pre[b]∣+L<=mid
然后我们根据这两个值给直径上的点排个序，枚举 i 点，扫描 j 点，把不满足第一个式子的点对的 4 中组合给 4 个 limitlimit 取 max/minmax/min
最后我们两个指针去找 a 和 b 就好了，找到就立个 flag …

#include<bits/stdc++.h>
#define Rg register
#define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(Rg int i=(a),I=(b)-1;i>I;--i)
#define go(G,u) for(Rg int i=G.head[u],v=G.e[i].to;i;v=G.e[i=G.e[i].nxt].to)
#define P pair<ll,int>
#define ll long long
using namespace std;
const ll inf=1e18+7;
const int M=1e5+3;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline bool cmax(ll& a,ll b){return a<b?a=b,1:0;}
inline bool cmin(ll& a,ll b){return a>b?a=b,1:0;}
inline int read(){ int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} int T,n,L,u,v,xb,frm[M],a[M],vis[M];
ll l,r,m,md,le[M],di[M]; P b[M],c[M];
struct Gr{ int pat,head[M];
    struct Edge{ int to,val,nxt; }e[M<<1];
    inline void clear(int n){
        pat=1,memset(head,0,(n+2)<<2);
    }
    inline void add(int u,int v,int w){
        e[++pat]={v,w,head[u]},head[u]=pat;
        e[++pat]={u,w,head[v]},head[v]=pat;
    }
}G;
void dfs(int u,int fa,ll d){
    if(d>md) md=d,v=u;
    go(G,u) if(v^fa&&!vis[i>>1])
        frm[v]=i,dfs(v,u,d+G.e[i].val);
}
int main(){
    while(1){ n=read(),L=read();
        if(!n) return 0; int x,y,z,i,flg;
        G.clear(n),memset(vis,0,n<<2);
        fp(i,2,n) x=read(),y=read(),
            z=read(),G.add(x,y,z);
        md=0,dfs(1,0,0),md=0,u=v,dfs(v,0,0);
        for(i=v,xb=0;i^u;i=G.e[frm[i]^1].to)
            vis[frm[i]>>1]|=1,a[++xb]=i,
            di[xb+1]=di[xb]+G.e[frm[i]].val;
        a[++xb]=i;
        fp(i,1,xb) md=0,dfs(a[i],0,0),le[i]=md,
            c[i]=P(le[i]+di[i],i),b[i]=P(le[i]-di[i],i);
        sort(b+1,b+1+xb),sort(c+1,c+1+xb);
        for(l=le[xb],r=di[xb];l<r;flg?r=m:l=m+1){
            ll A=-inf,B=inf,C=-inf,D=inf,aa=-inf,bb=inf; flg=0,m=(l+r)>>1;
            for(Rg int i=1,j=xb+1;i<=xb;++i){
                for(;j>1&&c[j-1].first+b[i].first>m;) u=c[--j].second,
                    cmax(aa,di[u]+le[u]),cmin(bb,di[u]-le[u]); u=b[i].second;
                cmax(A,L-m+le[u]+di[u]+aa),cmin(B,m-L+di[u]-le[u]+bb);
                cmax(C,le[u]-di[u]+L-m+aa),cmin(D,m-L-di[u]-le[u]+bb);
            }
            if(A>B||C>D){l=m+1;continue;}
            Rg int i,j,k,p,q;
            for(i=j=k=1,p=q=xb;!flg&&i<=xb;++i){
                while(j<i&&di[i]-di[j+1]>=C)++j;
                while(di[i]-di[k]>D)++k;
                while(p&&di[i]+di[p-1]>=A)--p;
                while(q&&di[i]+di[q]>B)--q;
                if(di[i]-di[j]>=C&&di[i]-di[k]<=D&&di[i]+di[p]>=A
                    &&di[i]+di[q]<=B&&Max(k,p)<=Min(j,q)) flg=1;
            }
        } printf("%lld\n",l);
    }
}  

拜拜…
PS：请大家围观【十一维的质子】，有消息第一时间留言，谢谢！