P4069 [SDOI2016] 游戏

题目描述

Alice 和 Bob 在玩一个游戏。

游戏在一棵有 \(n\) 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 \(123456789123456789\)。

有时，Alice 会选择一条从 \(s\) 到 \(t\) 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 \(r\)，若 \(r\) 与 \(s\) 的距离是 \(dis\)，那么 Alice 在点 \(r\) 上添加的数字是 \(a\times dis+b\)。

有时，Bob 会选择一条从 \(s\) 到 \(t\) 的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。

Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

数据范围

对于所有数据，\(n\le 10^5,0\le w, |b|\le 10^9\)。

Solution:

这下不得不在机房打 game 了

看到树上路径问题我们不难想到树链剖分.

看到贡献 \(y=k*dis+b\) 很难不想到李超线段树，我们把一条路径拆成上行链和下行链：(s,lca),(lca,t)

我们以 \(dfn\) 为x轴，贡献为y轴建立李超线段树，那么在该坐标系下的一条直线的表达式其实是 ：
\(y=k*dis[rid_{x}]+b\)
由于 \(dis\) 关于 \(dfn\) 的函数在每一条重链上是单调的，所以我们也就能保证插入的这条线段是单调的。

然后我们仔细的思考一下贡献：

对于上行链:
\(y=(-k)x+(dis_s*k+b)\)
对于下行链:
\(y=(k)x+(dis_s+2dis_{lca}+b)\)

然后要注意一下的是，由于这题我们需要区间查询，所以我们在 query 时需要注意查询的边界问题，详见代码。

然后这题就换乐的做完了。

Code:

#include<bits/stdc++.h>
#define ll long long
#define int long long
const ll inf=123456789123456789;
const int N=1e5+5;
using namespace std;
int n,m,tot;
ll dis[N],dep[N],dfn[N],fa[N],top[N],son[N],siz[N],rid[N];
struct line{
    ll k,b;
}q[N*20];
inline ll hight(ll x,int id)
{
    return q[id].k*(dis[rid[x]])+q[id].b;
}
inline ll Min(ll x,ll y){return x<y ? x : y;}
struct Segment_Tree{
    struct Tree{
        int id;
        ll ans;
    }t[N<<2];
    #define ls x<<1
    #define rs x<<1|1
    void build(int x,int l,int r)
    {
        t[x].ans=inf;
        if(l==r)return ;
        int mid=l+r>>1;
        build(ls,l,mid);build(rs,mid+1,r);
    }
    void pushup(int x){t[x].ans=Min(t[x].ans,Min(t[ls].ans,t[rs].ans));}
    void upd(int x,int l,int r,int L,int R,int k)
    {
        int mid=l+r>>1;
        if(L<=l&&r<=R)
        {
            ll h0=hight(l,t[x].id),h1=hight(mid,t[x].id),h2=hight(r,t[x].id);
            ll H0=hight(l,k),H1=hight(mid,k),H2=hight(r,k);
            t[x].ans=Min(t[x].ans,Min(H0,H2));
            if(H0<h0&&H2<h2){t[x].id=k;return ;}
            if(H0>=h0&&H2>=h2){return ;}
            if(q[k].k<q[t[x].id].k)
            {
                if(H1<h1){upd(ls,l,mid,L,R,t[x].id);t[x].id=k;}
                else upd(rs,mid+1,r,L,R,k);
            }
            else
            {
                if(H1<h1){upd(rs,mid+1,r,L,R,t[x].id);t[x].id=k;}
                else upd(ls,l,mid,L,R,k);
            }
        }
        if(L<=mid)upd(ls,l,mid,L,R,k);
        if(mid<R) upd(rs,mid+1,r,L,R,k);
        pushup(x);
        return ;
    }
    void query(int x,int l,int r,int L,int R,ll &res)
    {
        if(L<=l&&r<=R){res=Min(res,t[x].ans);return ;}
        ll tmp=Min(hight(max(l,L),t[x].id),hight(min(r,R),t[x].id));
        if(t[x].id)res=Min(res,tmp);
        int mid=l+r>>1;
        if(L<=mid)query(ls,l,mid,L,R,res);
        if(mid<R) query(rs,mid+1,r,L,R,res);
    }
    #undef ls
    #undef rs
}T;
struct Node{
    int y;
    ll w;
};
vector<Node> E[N];
void dfs1(int x,int ff)
{
    dep[x]=dep[ff]+1;fa[x]=ff;siz[x]=1;
    for(Node u : E[x])
    {
        if(u.y==fa[x])continue;
        dis[u.y]=dis[x]+u.w;
        dfs1(u.y,x);
        siz[x]+=siz[u.y];
        son[x] = siz[son[x]] > siz[u.y] ? son[x] : u.y;
    }
}
void dfs2(int x,int tp)
{
    dfn[x]=++dfn[0];top[x]=tp;rid[dfn[0]]=x;
    if(!son[x])return ;
    dfs2(son[x],tp);
    for(Node u : E[x])
    {
        if(u.y==fa[x]||u.y==son[x])continue;
        dfs2(u.y,u.y);
    }
}
int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y] ? x : y;
}
void chain_upd(int x,int y)
{
    while(top[x]!=top[y])
    {
        T.upd(1,1,n,dfn[top[x]],dfn[x],tot);
        x=fa[top[x]];
    }
    T.upd(1,1,n,dfn[y],dfn[x],tot);
}
ll chain_query(int s,int t)
{
    int lca=LCA(s,t),x=s,y=t;
    ll res=inf;
    while(top[x]!=top[lca])
    {
        T.query(1,1,n,dfn[top[x]],dfn[x],res);
        x=fa[top[x]];
    }
    while(top[y]!=top[lca])
    {
        T.query(1,1,n,dfn[top[y]],dfn[y],res);
        y=fa[top[y]];
    }
    if(dfn[x]<dfn[y])
    {
        T.query(1,1,n,dfn[x],dfn[y],res);
    }
    else
    {
        T.query(1,1,n,dfn[y],dfn[x],res);
    }
    return res;
}
void work()
{
    cin>>n>>m;
    for(int i=1,x,y;i<n;i++)
    {
        ll w;
        cin>>x>>y>>w;
        E[x].push_back({y,w});
        E[y].push_back({x,w});
    }
    dfs1(1,0);dfs2(1,1);
    T.build(1,1,n);
    q[tot]={0,inf};
    for(int i=1,opt,s,t;i<=m;i++)
    {
        ll k,b;
        cin>>opt>>s>>t;
        int lca=LCA(s,t);
        if(opt&1)
        {
            cin>>k>>b;
            q[++tot]={-k,k*dis[s]+b};chain_upd(s,lca);
            q[++tot]={k,k*(dis[s]-dis[lca]*2)+b};chain_upd(t,lca);
        }
        else
        {
            ll ans=chain_query(s,t);
            printf("%lld\n",ans);
        }
    }
}
#undef ll
#undef int
int main()
{
    //freopen("P4069.in","r",stdin);
    //freopen("P4069.out","w",stdout);
    work();
    return 0;
}