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
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
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);
}
}
}