题面

题解

如果我们把路径拆成两段，那么这个路径加可以看成是一个一次函数

具体来说，设\(dis_u\)表示节点\(u\)到根节点的距离，那么\((x,lca)\)这条路径上每个节点的权值就会加上\(-dis_ua+dis_xa+b\)，而\((lca,y)\)这条路径上每个节点就会加上\(dis_ua+a(dis_x+2\times dis_{lca})+b\)

区间加一次函数并维护最值，就是李超线段树啦~~~~

我们把它给树剖了，那么同一条重链里\(dis\)肯定是递增的，我们就可以把插入直线变成插入线段

顺便注意我们的线段树上的节点是离散化之后的，所以在李超线段树计算的时候要用原来的\(dis\)进行计算

树剖一个\(\log\)，李超线段树两个\(\log\)，总复杂度是\(O(n\log^3n)\)

我很好奇为啥这个复杂度都能跑过去啊……

//minamoto#include
    
     #define R register#define ll long long#define inf 123456789123456789ll#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R ll x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=1e5+5;struct eg{int v,nx,w;}e[N<<1];int head[N],tot;inline void add(R int u,R int v,R int w){e[++tot]={v,head[u],w},head[u]=tot;}ll dis[N],bb,kk;int dfn[N],rk[N],top[N],fa[N],sz[N],son[N],dep[N];int n,m,cnt;void dfs1(int u){    dep[u]=dep[fa[u]]+1,sz[u]=1;    go(u)if(v!=fa[u]){        fa[v]=u,dis[v]=dis[u]+e[i].w,dfs1(v),sz[u]+=sz[v];        sz[v]>sz[son[u]]?son[u]=v:0;    }}void dfs2(int u,int t){    rk[dfn[u]=++cnt]=u,top[u]=t;    if(!son[u])return;    dfs2(son[u],t);    go(u)if(!top[v])dfs2(v,v);}int LCA(R int u,R int v){    while(top[u]!=top[v]){        if(dep[top[u]]
       
        mn),cmin(mn,rc->mn);}    inline ll calc(R ll x){return k*x+b;}}pool[N<<2],*rt;int num;inline node *newnode(){return &pool[num++];}int ql,qr;ll res,k,b;void build(node* &p,int l,int r){    p=newnode(),p->b=p->mn=p->lv=p->rv=inf,p->k=0;    if(l==r)return;    int mid=(l+r)>>1;    build(p->lc,l,mid),build(p->rc,mid+1,r);}void update(node *p,int l,int r,ll b,ll k){    if(ql<=l&&qr>=r){        int mid=(l+r)>>1;        ll dl=dis[rk[l]],dr=dis[rk[r]],dm=dis[rk[mid]];        if(!p->flag)return p->ins(b,k,dl,dr),void();        ll lv=dl*k+b,rv=dr*k+b;        if(lv>=p->lv&&rv>=p->rv)return;        if(lv
        
         lv&&rv
         
          rv)return p->ins(b,k,dl,dr),void(); double x=1.0*(b-p->b)/(p->k-k); if(lv<=p->lv){ if(x<=dm)update(p->lc,l,mid,b,k); else bb=p->b,kk=p->k,p->ins(b,k,dl,dr),update(p->rc,mid+1,r,bb,kk); }else{ if(x<=dm)bb=p->b,kk=p->k,p->ins(b,k,dl,dr),update(p->lc,l,mid,bb,kk); else update(p->rc,mid+1,r,b,k); } p->upd(); return; } int mid=(l+r)>>1; if(ql<=mid)update(p->lc,l,mid,b,k); if(qr>mid)update(p->rc,mid+1,r,b,k); p->upd();}void query(node *p,int l,int r){ if(ql<=l&&qr>=r)return cmin(res,p->mn),void(); cmin(res,p->calc(dis[rk[max(l,ql)]])), cmin(res,p->calc(dis[rk[min(r,qr)]])); int mid=(l+r)>>1; if(ql<=mid)query(p->lc,l,mid); if(qr>mid)query(p->rc,mid+1,r);}void change(int u,int v){ while(top[u]!=top[v]){ ql=dfn[top[u]],qr=dfn[u], update(rt,1,n,b,k), u=fa[top[u]]; } ql=dfn[v],qr=dfn[u],update(rt,1,n,b,k);}void ask(int u,int v){ res=inf; while(top[u]!=top[v]){ if(dep[top[u]]