题解：P7359 「JZOI-1」旅行

qzmoot · 2025-09-26 21:22:07 · 题解

题解：P7359 「JZOI-1」旅行

题目大意

你在经过一条边的时候可以顺水过去，或者走路过去，从陆地行走变成坐船需要一定的时间。\ 有多组询问，给定起点和终点，询问最短时间。

题目分析

可以看出是一道动态 dp 问题。先考虑朴素转移。注意到我们在转移的时候只会有两种状态，一种是在陆地，一种在水里，于是令状态为 f_{i,0/1}。\ 那么先写出从儿子走到祖先的转移方程。

注意一下啊，这里的 z 是带符号的，也就是顺水的话为负号，否则为正号。

你可能会不知道这两个转移是为什么：

这是很反生活常识的，第一个是你可以在陆地上的时候造船，然后再坐船过去，再丢掉船，第二个是你可以在水上的时候可以丢掉船，先走路再造船。

于是你就写出了普通转移，那么熟知矩阵乘法的你就知道，这里要使用广义矩阵乘法和动态 dp 来写了。

简单介绍一下动态 dp，对于需要多次跑 dp 的题目，且复杂度不支持跑多次，并且是递推转移的情况。那么对于这道题来说，你可以把每次的转移矩阵记下来，然后写一个数据结构支持查询区间的转移矩阵乘积即可。

那么接下来的我们就可以书写转移矩阵了。

这样，我们就处理完了从儿子到祖先的 dp。接下来就是从祖先到儿子的。

注意到两者的本质是相同的，对于固定的 u,v 来说，后者走过的边全是前者走过的边，只不过 z 值变成相反数了，然后转移顺序变成了从上到下。

欸，这个从上到下不就是我们第一个矩阵转移的反方向吗，那我们对 z 的相反值求个逆序矩阵不就是从祖先到儿子的答案了吗？

直接上树剖线段树维护树上路径的值即可。于是本题思路到此为止。

细节

感觉动态 dp 的细节都很多。比如此题你将对应的值存入初始矩阵就比较麻烦，容易存反符号。

然后就是实现树剖线段树维护矩阵的时候，注意两个矩阵的顺序是不同的，所以在 push_up 和 query 的时候，答案的合并是不同的。

并且相对于普通的树剖线段树来说，这道题目是边权并非点权，于是我们只能将父亲到自己边的权值存在当前点中。那么在求答案的过程中，我们就不能取两个点 \operatorname{lca} 的点权值。

然后因为顺序问题，我分别写了两个函数求两种类型的贡献值，注意初始时 f_0=0,f_1=L。

CODE

#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
constexpr int N=2e5+5,inf=1e18;
int n,L,T;
vector<tuple<int,int,int>>e[N];
pii w1[N],w2[N];
struct mat{
    int a00,a01,a10,a11;
    inline void set(){a00=a11=0,a01=a10=inf;}
    mat(){}
    mat(int a,int b,int c,int d):a00(a),a01(b),a10(c),a11(d){}
};
inline mat operator*(const mat& x,const mat& y)
{
    mat res=mat(inf,inf,inf,inf);
    res.a00=min(res.a00,x.a00+y.a00);
    res.a00=min(res.a00,x.a01+y.a10);
    res.a01=min(res.a01,x.a00+y.a01);
    res.a01=min(res.a01,x.a01+y.a11);
    res.a10=min(res.a10,x.a10+y.a00);
    res.a10=min(res.a10,x.a11+y.a10);
    res.a11=min(res.a11,x.a10+y.a01);
    res.a11=min(res.a11,x.a11+y.a11);
    return res;
}
int fa[N],dep[N],dfn[N],idx,id[N];
int siz[N],son[N],top[N];
void dfs1(int u,int fa)
{
    ::fa[u]=fa,dep[u]=dep[fa]+1,siz[u]=1;
    for(auto nxt:e[u])
    {
        int v,a,z;
        tie(v,a,z)=nxt;
        if(v==fa)continue;
        w1[v]=mp(a,-z),w2[v]=mp(a,z);
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])
            son[u]=v;
    }
}
void dfs2(int u,int top)
{
    ::top[u]=top,dfn[u]=++idx,id[idx]=u;
    if(son[u])dfs2(son[u],top);
    for(auto nxt:e[u])
    {
        int v,a,z;
        tie(v,a,z)=nxt;
        if(v==fa[u] || v==son[u])continue;
        dfs2(v,v);
    }
}
inline int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]>dep[v]?v:u;
}
struct node{
    mat a1,a2;
}tr[N<<2];
#define ls k<<1
#define rs k<<1|1
inline void pu(int k)
{
    tr[k].a1=tr[ls].a1*tr[rs].a1;//v->u
    tr[k].a2=tr[rs].a2*tr[ls].a2;//u->v
}
void build(int k,int l,int r)
{
    if(l==r)
    {
#define i id[l]
        tr[k].a1=mat(min(w1[i].fi,w1[i].fi+L+w1[i].se),w1[i].fi+w1[i].se,L+w1[i].fi+w1[i].se,min(w1[i].fi+w1[i].se,w1[i].fi+L));
        tr[k].a2=mat(min(w2[i].fi,w2[i].fi+L+w2[i].se),w2[i].fi+w2[i].se,L+w2[i].fi+w2[i].se,min(w2[i].fi+w2[i].se,w2[i].fi+L));
#undef i
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pu(k);
}
mat query1(int k,int l,int r,int L,int R)
{
    mat res;
    res.set();
    if(r<L || R<l)
        return res;
    if(L<=l && r<=R)
        return tr[k].a1;
    int mid=l+r>>1;
    return query1(ls,l,mid,L,R)*query1(rs,mid+1,r,L,R);
}
mat query2(int k,int l,int r,int L,int R)
{
    mat res;
    res.set();
    if(r<L || R<l)
        return res;
    if(L<=l && r<=R)
        return tr[k].a2;
    int mid=l+r>>1;
    return query2(rs,mid+1,r,L,R)*query2(ls,l,mid,L,R);
}
#undef ls
#undef rs
void solve1(int u,int v,mat& ans)
{
    if(u==v)return;
    mat res;
    res.set();
    while(top[u]!=top[v])
        res=query1(1,1,n,dfn[top[u]],dfn[u])*res,u=fa[top[u]];
    res=query1(1,1,n,dfn[v]+1,dfn[u])*res;
    ans=res*ans;
}
void solve2(int u,int v,mat& ans)
{
    if(u==v)return;
    mat res;
    res.set();
    while(top[u]!=top[v])
        res=res*query2(1,1,n,dfn[top[u]],dfn[u]),u=fa[top[u]];
    res=res*query2(1,1,n,dfn[v]+1,dfn[u]);
    ans=res*ans;
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in","r",stdin);
//  freopen("wa.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>L>>T;
    for(int i=1,u,v,a,z,typ;i<n;i++)
        cin>>u>>v>>a>>z>>typ,e[u].pb(v,a,z*(typ?-1:1)),e[v].pb(u,a,z*(typ?1:-1));
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(T--)
    {
        int u,v;
        cin>>u>>v;
        int l=lca(u,v);
        mat ans=mat(0,0,L,0);
        solve1(u,l,ans);
        solve2(v,l,ans);
        cout<<min(ans.a00,ans.a10)<<'\n';
    }
    return 0;
}