[SDOI2016]游戏

Description

Alice 和 Bob 在玩一个游戏。游戏在一棵有 n 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 123456789123456789。有时，Alice 会选择一条从 s 到 t 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r，若 r 与 s 的距离是 dis，那么 Alice 在点 r 上添加的数字是 a×dis+b。有时，Bob 会选择一条从 s 到 t 的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

Input

第一行两个数字 n、m，表示树的点数和进行的操作数。接下来 n−1 行，每行三个数字 u、v、w，表示树上有一条连接 u、v 的边，长度是 w。接下来 m 行。每行第一个数字是 1 或 2。若第一个数是 1，表示 Alice 进行操作，接下来四个数字 s、t、a、b。若第一个数是 2，表示 Bob 进行操作，接下来四个数字 s、t。

Output

每当 Bob 进行操作，输出一行一个数，表示他能够选择的最小的数字

Sample Input

3 5
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
2 2 3

Sample Output

123456789123456789
6
-106

HINT

n≤100000，m≤100000，∣a∣≤10000,0<=w，|b|<=10^9

对于A*dis+B，将它分成s->lca,lca->t

s->lca:

A*(d[s]-d[x])+B=-A*d[x]+A*d[s]+B

lca->t:

A*(d[s]+d[x]-2*d[lca])+B=A*d[x]+A*d[s]-2*A*d[lca]+B

在一条链上显然d[fa]<d[son]，所以相当于把一个一次函数放入几个线段

查询就是求区间线段最小值

然后就是lichao线段树

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #include<algorithm>
 using namespace std;
 typedef long long lol;
 struct Node
 {
   int next,to;
   lol dis;
 }edge[];
 struct Line
 {
   lol k,b;
   bool id;
 }tree[];
 lol ans,d[],val[],inf=;
 int num,head[],size[],fa[][],dep[],son[],dfn[],cnt,id[],top[],n,m;
 void add(int u,int v,lol w)
 {
   num++;
   edge[num].next=head[u];
   head[u]=num;
   edge[num].to=v;
   edge[num].dis=w;
 }
 void dfs1(int x,int pa)
 {int i;
   size[x]=;
   for (i=head[x];i;i=edge[i].next)
     {
       int v=edge[i].to;
       if (v==pa) continue;
       fa[v][]=x;
       d[v]=d[x]+edge[i].dis;
       dep[v]=dep[x]+;
       dfs1(v,x);
       size[x]+=size[v];
       if (size[v]>size[son[x]]) son[x]=v;
     }
 }
 void dfs2(int x,int pa,int tp)
 {int i;
   dfn[x]=++cnt;
   id[cnt]=x;
   top[x]=tp;
   if (son[x]) dfs2(son[x],x,tp);
   for (i=head[x];i;i=edge[i].next)
     {
       int v=edge[i].to;
       if (v==pa||v==son[x]) continue;
       dfs2(v,x,v);
     }
 }
 int lca(int x,int y)
 {
   while (top[x]!=top[y])
     {
       if (d[top[x]]<d[top[y]]) swap(x,y);
       x=fa[top[x]][];
     }
   if (d[x]<d[y]) return x;
   else return y;
 }
 lol cal(Line a,lol x)
 {
   return a.k*x+a.b;
 }
 double cross(Line x,Line y)
 {
   return (x.b-y.b)/(1.0*(y.k-x.k));
 }
 void add_min(int rt,int l,int r,Line x)
 {
   if (!tree[rt].id)
     {
       tree[rt]=x;
       return;
     }
   lol f1=cal(x,d[id[l]]);lol f2=cal(tree[rt],d[id[l]]);
   lol f3=cal(x,d[id[r]]);lol f4=cal(tree[rt],d[id[r]]);
   if (f1>=f2&&f3>=f4) return;
   else
     if (f1<=f2&&f3<=f4)
       {tree[rt]=x;}
     else
       {
     double p=cross(tree[rt],x);
     int mid=(l+r)/;
     if (f1<=f2)
       {
         if (p<=d[id[mid]]) add_min(rt<<,l,mid,x);
         else add_min(rt<<|,mid+,r,tree[rt]),tree[rt]=x;
       }
     else
       {
         if (p<=d[id[mid]]) add_min(rt<<,l,mid,tree[rt]),tree[rt]=x;
         else add_min(rt<<|,mid+,r,x);
       }
       }
 }
 void update(int rt,int l,int r,int L,int R,Line x)
 {
     val[rt]=min(val[rt],min(cal(x,d[id[L]]),cal(x,d[id[R]])));
   if (l==L&&r==R)
     {
       add_min(rt,l,r,x);
       return;
     }
   int mid=(l+r)/;
   if (R<=mid) update(rt<<,l,mid,L,R,x);
   else if (L>mid) update(rt<<|,mid+,r,L,R,x);
   else
     {
       update(rt<<,l,mid,L,mid,x);
       update(rt<<|,mid+,r,mid+,R,x);
     }
 }
 void query(int rt,int l,int r,int L,int R)
 {
   if (tree[rt].id)
     {
       ans=min(ans,min(cal(tree[rt],d[id[L]]),cal(tree[rt],d[id[R]])));
     }
   if (l==L&&r==R)
     {
       ans=min(ans,val[rt]);
       return;
     }
   int mid=(l+r)/;
   if (R<=mid) query(rt<<,l,mid,L,R);
   else if (L>mid) query(rt<<|,mid+,r,L,R);
   else
     {
       query(rt<<,l,mid,L,mid);query(rt<<|,mid+,r,mid+,R);
     }
 }
 void build(int rt,int l,int r)
 {
   val[rt]=inf;
   if (l==r) return;
   int mid=(l+r)/;
   build(rt*,l,mid);
   build(rt*+,mid+,r);
 }
 int main()
 {int i,u,v,j,opt,s,t,x,y;
   lol w,A,B;
   cin>>n>>m;
   for (i=;i<=n-;i++)
     {
       scanf("%d%d%lld",&u,&v,&w);
       add(u,v,w);add(v,u,w);
     }
   dfs1(,);
   dfs2(,,);
   for (i=;i<=;i++)
     {
       for (j=;j<=n;j++)
     fa[j][i]=fa[fa[j][i-]][i-];
     }
   build(,,n);
   for (i=;i<=m;i++)
     {
       scanf("%d",&opt);
       if (opt==)
     {
       scanf("%d%d%lld%lld",&s,&t,&A,&B);
       int z=lca(s,t);
       x=s;y=t;
       while (top[x]!=top[z])
         {
           update(,,n,dfn[top[x]],dfn[x],(Line){-A,B+A*d[s],});
           x=fa[top[x]][];
         }
       update(,,n,dfn[z],dfn[x],(Line){-A,B+A*d[s],});
       while (top[y]!=top[z])
         {
           update(,,n,dfn[top[y]],dfn[y],(Line){A,B-*A*d[z]+A*d[s],});
           y=fa[top[y]][];
         }
       update(,,n,dfn[z],dfn[y],(Line){A,B-*A*d[z]+A*d[s],});
     }
       else
     {
       scanf("%d%d",&s,&t);
       int z=lca(s,t);
       x=s;y=t;ans=inf;
       while (top[x]!=top[z])
         {
           query(,,n,dfn[top[x]],dfn[x]);
           x=fa[top[x]][];
         }
       query(,,n,dfn[z],dfn[x]);
       while (top[y]!=top[z])
         {
           query(,,n,dfn[top[y]],dfn[y]);
           y=fa[top[y]][];
         }
       query(,,n,dfn[z],dfn[y]);
       printf("%lld\n",ans);
     }
     }
 }