【BZOJ-4515】游戏 李超线段树 + 树链剖分 + 半平面交

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long read()
{
    long long x=0,f=1; char ch=getchar();
    while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘)f=-1; ch=getchar();}
    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
    return x*f;
}
#define maxn 100100
struct EdgeNode{int next,to;long long len;}edge[maxn<<1];
int head[maxn],cnt;
void add(int u,int v,long long w)
{
    cnt++;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].len=w;
}
void insert(int u,int v,long long w) {add(u,v,w); add(v,u,w);}
int n,m;
//--------------------------------------------------------------------------------------------------------
int pl[maxn],sz,pr[maxn],size[maxn],deep[maxn],son[maxn],top[maxn],fa[maxn];long long dis[maxn],pre[maxn];
void dfs_1(int x)
{
    size[x]=1;
    for (int i=head[x]; i; i=edge[i].next) 
        if (edge[i].to!=fa[x])
            {
                fa[edge[i].to]=x;
                deep[edge[i].to]=deep[x]+1;
                dis[edge[i].to]=dis[x]+edge[i].len;
                dfs_1(edge[i].to);
                if (size[son[x]]<size[edge[i].to]) son[x]=edge[i].to;
                size[x]+=size[edge[i].to];
            }
}
void dfs_2(int x,int chain)
{
    pl[x]=++sz; pre[sz]=dis[x]; top[x]=chain; 
    if (son[x]) dfs_2(son[x],chain);
    for (int i=head[x]; i; i=edge[i].next)
        if (edge[i].to!=fa[x] && edge[i].to!=son[x])
            dfs_2(edge[i].to,edge[i].to);
    pr[x]=sz;
}
int LCA(int x,int y)
{
    while (top[x]!=top[y])
    {
        if (deep[top[x]]<deep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }   
    if (deep[x]>deep[y]) swap(x,y);
    return x;
}
//--------------------------------------------------------------------------------------------------------
long long f(long long x,long long k,long long b) {return k*x+b;}
struct TreeNode{long long a,b,minn;}tree[maxn<<2];
#define inf 123456789123456789LL
void Build(int now,int l,int r)
{
    tree[now].a=0; tree[now].b=tree[now].minn=inf;
    if (l==r) return;
    int mid=(l+r)>>1;
    Build(now<<1,l,mid); Build(now<<1|1,mid+1,r);
} 
long long Query(int now,int l,int r,int L,int R)
{
    long long re=min(f(pre[L],tree[now].a,tree[now].b),f(pre[R],tree[now].a,tree[now].b));
    if (l==L && r==R) return min(re,tree[now].minn);
    int mid=(l+r)>>1; 
    if (R<=mid) return min(re,Query(now<<1,l,mid,L,R)); 
        else if (L>mid) return min(re,Query(now<<1|1,mid+1,r,L,R)); 
            else return min(re,min(Query(now<<1,l,mid,L,mid),Query(now<<1|1,mid+1,r,mid+1,R)));
}
void Change(int now,int l,int r,long long a,long long b)
{
    int mid=(l+r)>>1,fl,fr,fm;
    fl=(f(pre[l],tree[now].a,tree[now].b)>f(pre[l],a,b));
    fr=(f(pre[r],tree[now].a,tree[now].b)>f(pre[r],a,b));
    fm=(f(pre[mid],tree[now].a,tree[now].b)>f(pre[mid],a,b));
    if (fl&fr&fm)
        {
            tree[now].a=a;tree[now].b=b;tree[now].minn=min(tree[now].minn,min(f(pre[l],a,b),f(pre[r],a,b)));
            return;
        }
    if (!(fl|fr|fm)) return;
    if (fm)
        {
            if (fr) Change(now<<1,l,mid,tree[now].a,tree[now].b);
                else Change(now<<1|1,mid+1,r,tree[now].a,tree[now].b);
            tree[now].a=a;tree[now].b=b;tree[now].minn=min(tree[now].minn,min(f(pre[l],a,b),f(pre[r],a,b)));
        }
    if (!fm)
        if (!fr) Change(now<<1,l,mid,a,b);
            else Change(now<<1|1,mid+1,r,a,b);
    tree[now].minn=min(tree[now].minn,min(tree[now<<1].minn,tree[now<<1|1].minn));
}
void change(int now,int l,int r,int L,int R,long long a,long long b)
{
    if (L<=l && R>=r) {Change(now,l,r,a,b); return;}
    int mid=(l+r)>>1;
    if (L<=mid) change(now<<1,l,mid,L,R,a,b); 
    if (R>mid) change(now<<1|1,mid+1,r,L,R,a,b);
    tree[now].minn=min(tree[now].minn,min(tree[now<<1].minn,tree[now<<1|1].minn));
}
//--------------------------------------------------------------------------------------------------------
void Solve_Insert(int s,int t,long long a,long long b)
{
    int lca=LCA(s,t); int x=s,y=t;
    while (top[x]!=top[lca])
        {
            change(1,1,n,pl[top[x]],pl[x],-a,a*dis[s]+b);
            x=fa[top[x]];
        }
    change(1,1,n,pl[lca],pl[x],-a,a*dis[s]+b);
    while (top[y]!=top[lca])
        {
            change(1,1,n,pl[top[y]],pl[y],a,dis[s]*a-dis[lca]*2*a+b);
            y=fa[top[y]];
        }
    if (y!=lca) change(1,1,n,pl[lca]+1,pl[y],a,dis[s]*a-dis[lca]*2*a+b);
}
long long Solve_Query(int s,int t)
{
    int x=s,y=t; long long re=inf;
    while (top[x]!=top[y])
        {
            if (deep[top[x]]<deep[top[y]]) swap(x,y);
            re=min(Query(1,1,n,pl[top[x]],pl[x]),re);
            x=fa[top[x]];
        }
    if (deep[x]>deep[y]) swap(x,y);
    re=min(Query(1,1,n,pl[x],pl[y]),re);
    return re;
}
//--------------------------------------------------------------------------------------------------------
int main()
{
//    freopen("menci_game.in","r",stdin);
//    freopen("menci_game.out","w",stdout);
    n=read();m=read(); long long w;
    for (int u,v,i=1; i<=n-1; i++)
        u=read(),v=read(),w=(long long)read(),insert(u,v,w);
    dfs_1(1); dfs_2(1,1); Build(1,1,n);
    while (m--)
        {
            int opt=read();
            if (opt==1)
                {
                    int s=read(),t=read();long long a=read(),b=read();
                    Solve_Insert(s,t,a,b);
                }
            if (opt==2)
                {
                    int s=read(),t=read();
                    printf("%lld\n",Solve_Query(s,t));
                }
        }
    return 0;
}