P4069 SDOI2016 游戏

传送门

solution

树剖后一段路径变成了若干链拼起来。自上而下和自下而上分别维护两棵李超线段树，每条链就是一段数轴，提前处理每个点两种方向上的在链内的横坐标。以最近公共祖先为界，把路径分成两段。从一个点向链的顶端跳就是区间加线段。每次跳完要把线段的截距增加一个横坐标偏移量乘上斜率，因为不同链横坐标不是统一的。

线段树要维护区间加线段和区间最值。每次插入线段都要用两端点更新区间的最值。每次查询 \([L,R]\) （设在链上横坐标为 \([Ls,Rs]\)）要在经过的所有区间把该区间和 \([Ls,Rs]\) 取交，然后用这个区间的最优线段（就是李超线段树维护的中点处取值最小的）在这个交区间的两端点的值更新答案。

建议先写链的情况（这个题数据链都是从 1 到 n 依次排点的），然后再上树。

建议写个暴力拍。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;

typedef long long E;
const E inf=123456789123456789;

struct line{
  E k,b;
  line(E a=0,E y=inf){ k=a,b=y; }
  inline E get(E x){ return k*x+b; }
};

const int N=400010;

struct segment{
  line dat[N<<2];
  E lp[N<<2],rp[N<<2],V[N<<2];

  void pushup(int u){ lp[u]=lp[u<<1],rp[u]=rp[u<<1|1]; }

  void build(int u,int l,int r,E *P){
    dat[u]=line(0,inf); V[u]=inf;
    if(l==r) return lp[u]=rp[u]=P[l],void();
    int mid=(l+r)>>1;
    build(u<<1,l,mid,P),build(u<<1|1,mid+1,r,P);
    pushup(u);
  }

  void ins(int u,int l,int r,line val){
    if(val.get(lp[u])>=dat[u].get(lp[u])&&
       val.get(rp[u])>=dat[u].get(rp[u])) return ;

    int mid=(l+r)>>1,h=(lp[u]==rp[u]?lp[u]:rp[u<<1]);
    if(val.get(h)<dat[u].get(h)) swap(val,dat[u]);
    V[u]=min({V[u],dat[u].get(lp[u]),dat[u].get(rp[u])});
    //cout<<"INS "<<l<<' '<<r<<' '<<V[u]<<endl;
    if(l==r) return ;
    if(val.get(lp[u])<dat[u].get(lp[u])) ins(u<<1,l,mid,val);
    if(val.get(rp[u])<dat[u].get(rp[u])) ins(u<<1|1,mid+1,r,val);
    V[u]=min({V[u],V[u<<1],V[u<<1|1]});
  }

  void add(int u,int l,int r,int L,int R,line val){
    if(L<=l&&r<=R) return ins(u,l,r,val);
    int mid=(l+r)>>1;
    if(L<=mid) add(u<<1,l,mid,L,R,val);
    if(mid<R) add(u<<1|1,mid+1,r,L,R,val);
    V[u]=min({V[u],V[u<<1],V[u<<1|1]});
    //cout<<"ADD "<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<V[u]<<endl;
  }

  E ask(int u,int l,int r,int L,int R,E Ls,E Rs,int op){
    if(L<=l&&r<=R){
      return V[u];
    }
    int mid=(l+r)>>1;
    E ret=inf;
    if(op==2) ret=min({ret,dat[u].get(max(Ls,lp[u])),dat[u].get(min(Rs,rp[u]))});
    else ret=min({ret,dat[u].get(min(Ls,lp[u])),dat[u].get(max(Rs,rp[u]))});
    if(mid<R) ret=min(ret,ask(u<<1|1,mid+1,r,L,R,Ls,Rs,op));
    if(L<=mid) ret=min(ret,ask(u<<1,l,mid,L,R,Ls,Rs,op));
    return ret;
  }

}seg1,seg2;

/*

- seg1 -> bottom to top

- seg2 -> top to bottom

*/

struct Edge{
  int nxt,to,val;
}e[N<<1];

int hd[N],idx=2;

inline void add(int a,int b,int c){
  e[idx].nxt=hd[a],e[idx].to=b,e[idx].val=c,hd[a]=idx++;
}

E dist[N];
int sz[N],dep[N],top[N],fa[N],hson[N],dfn[N],timestamp;
E mdep[N];
void dfs1(int u){
  sz[u]=1;
  for(int i=hd[u]; i; i=e[i].nxt){
    int j=e[i].to;
    if(j==fa[u]) continue;
    fa[j]=u; dep[j]=dep[u]+1; dist[j]=dist[u]+e[i].val;
    dfs1(j);
    sz[u]+=sz[j];
    if(sz[j]>sz[hson[u]]) hson[u]=j;
  }
}

void dfs2(int u){
  dfn[u]=++timestamp;
  if(sz[u]==1) return ;
  top[hson[u]]=top[u];
  dfs2(hson[u]);
  for(int i=hd[u]; i; i=e[i].nxt){
    int j=e[i].to;
    if(j==fa[u]||j==hson[u]) continue;
    top[j]=j;
    dfs2(j);
  }
}

int n,m;
E P[N];

inline void tree_add(int a,int b,line L){
  int x=a,y=b;
  while(top[x]!=top[y]){
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    x=fa[top[x]];
  }
  int lca=dep[x]<dep[y]?x:y;
  E d=dist[a]+dist[b]-2*dist[lca],D=0;
  while(top[a]!=top[b]){
    if(dep[top[a]]>dep[top[b]]){
      seg1.add(1,1,n,dfn[top[a]],dfn[a],line(L.k,L.b+(D-(mdep[top[a]]-dist[a]))*L.k));
      D+=dist[a]-dist[fa[top[a]]];
      a=fa[top[a]];
    }
    else{
      d-=(dist[b]-dist[top[b]]);
      seg2.add(1,1,n,dfn[top[b]],dfn[b],line(L.k,L.k*d+L.b));
      d-=(dist[top[b]]-dist[fa[top[b]]]);
      b=fa[top[b]];
    }
  }
  if(dep[a]>dep[b]){
    seg1.add(1,1,n,dfn[b],dfn[a],line(L.k,L.b+(D-(mdep[top[a]]-dist[a]))*L.k));
  }
  else{
    d-=(dist[b]-dist[a]);
    seg2.add(1,1,n,dfn[a],dfn[b],line(L.k,L.k*(d-(dist[a]-dist[top[b]]))+L.b));
  }
}

inline E tree_query(int a,int b){
  E ret=inf;
  while(top[a]!=top[b]){
    if(dep[top[a]]>dep[top[b]]){
      ret=min(ret,seg1.ask(1,1,n,dfn[top[a]],dfn[a],mdep[top[a]]-dist[top[a]],mdep[top[a]]-dist[a],1));
      ret=min(ret,seg2.ask(1,1,n,dfn[top[a]],dfn[a],0,dist[a]-dist[top[a]],2));
      a=fa[top[a]];
    }
    else{
      ret=min(ret,seg2.ask(1,1,n,dfn[top[b]],dfn[b],0,dist[b]-dist[top[b]],2));
      ret=min(ret,seg1.ask(1,1,n,dfn[top[b]],dfn[b],mdep[top[b]]-dist[top[b]],mdep[top[b]]-dist[b],1));
      b=fa[top[b]];
    }
  }
  if(dep[a]<dep[b]) swap(a,b);
  ret=min({ret,seg1.ask(1,1,n,dfn[b],dfn[a],mdep[top[b]]-dist[b],mdep[top[a]]-dist[a],1),
          seg2.ask(1,1,n,dfn[b],dfn[a],dist[b]-dist[top[b]],dist[a]-dist[top[a]],2)});
  return ret;
}

signed main(){
  cin>>n>>m;
  for(int i=1; i<n; i++){
    int u,v,w;
    scanf("%lld%lld%lld",&u,&v,&w);
    add(u,v,w),add(v,u,w);
  }

  dep[1]=top[1]=1;
  dfs1(1),dfs2(1);

  for(int i=1; i<=n; i++){
    mdep[top[i]]=max(mdep[top[i]],dist[i]);
  }
  for(int i=1; i<=n; i++){
    P[dfn[i]]=mdep[top[i]]-dist[i];
  }
  seg1.build(1,1,n,P);

  for(int i=1; i<=n; i++){
    P[dfn[i]]=dist[i]-dist[top[i]];
  }
  seg2.build(1,1,n,P);
  
/*
  for(int ttt=1; ttt<=m; ttt++){
    int opt,s,t,a,b;
    scanf("%lld%lld%lld",&opt,&s,&t);
    if(opt==1){
      scanf("%lld%lld",&a,&b);
      if(dfn[s]<=dfn[t]){
        seg2.add(1,1,n,dfn[s],dfn[t],line(a,b-a*dist[s]));
      }
      else seg1.add(1,1,n,dfn[t],dfn[s],line(a,b-a*(mdep[top[s]]-dist[s])));
    }
    else{
      if(dfn[s]>dfn[t]) swap(s,t);
      printf("%lld\n",min(seg1.ask(1,1,n,dfn[s],dfn[t],mdep[top[s]]-dist[s],mdep[top[s]]-dist[t],1),
                          seg2.ask(1,1,n,dfn[s],dfn[t],dist[s],dist[t],2)));
    }
  }

  return 0;
  
  链的情况
  
  */

  for(int ttt=0; ttt<m; ttt++){
    int opt,s,t,a,b;
    scanf("%lld%lld%lld",&opt,&s,&t);
    if(opt==1){
      scanf("%lld%lld",&a,&b);
      tree_add(s,t,line(a,b));
    }
    else{
      auto ans=tree_query(s,t);
      printf("%lld\n",ans);
    }
  }

  return 0;
}