---

记\(val_i\)是每条边的边权，\(s\)是边权和，\(t\)是经过边数，\(k\)是给定的\(k\)。

在点分治的时候二分答案\(x\)，设\(|\frac st-k|=x\)，判断是否还能满足\(|\frac st-k|<x\)。

因为是绝对值，分两种情况：

1. \(\frac st-k\geq 0\to \sum val_i-k\geq 0\)，
   判断是否有\(\frac st-k< x\to\quad s-t*k<t*x\to\quad\sum val_i-k<t*x\)。
2. \(\frac st-k<0\to\sum val_i-k<0\)，
   判断是否有\(\frac st-k>-x\to\quad s-t*k>-t*x\to\quad \sum val_i-k>-t*x\)

先对每条边的边权\(val_i\)减掉一个\(k\)。

以第一种情况为例，就是求是否存在两条路径\(i,j\)，使得\(s_i+s_j\geq 0\)，且\(s_i+s_j<t_i*x+t_j*x\)。

把\(DFS\)得到的子树路径信息存一个三元组\((s,t,anc)\)，表示一条路径的权值和、边数、这条路径来自哪棵子树（两条路径拼起来的时候不能来自同一棵子树）。

然后把所有三元组按\(s\)从小到大排序。那从小到大枚举\(i\)，第一个满足\(s_i+s_j\geq 0\)的\(j\)的位置一定是单调递减的，\(j\)后面（\(i\)之前）的路径都满足。

所以维护两个\(pair\)，表示两个\(s_k-t_k*x\)最小的、来自不同子树的三元组\(A,B\)。找到第一个\(s_p>0\)的位置\(p\)，令\(i=p,j=p-1\)，然后随着\(i\)的枚举，更新一下\(A,B\)，然后\(j\)也不断往前移动顺便更新\(A,B\)就可以了。每次对于\(i\)，就把\(A,B\)做\(k\)，与\(i\)组合一下看是否可以满足\(s_k-t_k*x<t_i*x-s_i\)。

具体看代码吧，

有两种情况就二分\(x\)的时候，用两个\(check\)判断\(x\)（\(\frac st -k\geq 0\)）和\(-x\)（\(\frac st-k<0\)）是否有一个可行就行了。

都是抄的一份代码 常数差距怎么就那么大呢

---

//6952kb    6680ms#include 
    
     #include 
     
      #include 
      
       #define mp std::make_pair#define pr std::pair
       
        //#define gc() getchar()#define MAXIN 300000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)typedef long long LL;const int N=5e4+5;const LL INF=1ll<<60;int cnt,Enum,H[N],nxt[N<<1],to[N<<1],Min,root,sz[N];LL Ans,len[N<<1];bool vis[N];char IN[MAXIN],*SS=IN,*TT=IN;struct Node{    LL s; int t,anc;    inline bool operator <(const Node &x)const    {        return s
        
         mx&&(mx=sz[v]);    mx=std::max(mx,tot-sz[x]);    if(mx
         
          =0) Upd(x,y,mp(A[j].s-k*A[j].t,A[j].anc)), --j; if((x.second==A[i].anc?y.first:x.first)+A[i].s
          
           -tx -> -s
           
            >1,p,cnt)||Check2(mid,p,cnt)) Ans=mid-1, r=mid-1; else l=mid+1; for(int i=H[x],v; i; i=nxt[i]) if(!vis[v=to[i]]) Min=N, FindRoot(v,x,sz[v]), Solve(root);}int main(){ const int n=read(); const LL K=readll();//readll!! Ans=INF;//在这 不能在Solve()前面 = = for(int i=1; i