专栏文章

题解：P7359 「JZOI-1」旅行

qqzmoot
P7359题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mins8vym
此快照首次捕获于
2025/12/02 07:30
3 个月前
此快照最后确认于
2025/12/02 07:30
3 个月前
查看原文

题解：P7359 「JZOI-1」旅行

题目大意

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

题目分析

可以看出是一道动态 dp 问题。先考虑朴素转移。注意到我们在转移的时候只会有两种状态，一种是在陆地，一种在水里，于是令状态为 fi,0/1f_{i,0/1}。
那么先写出从儿子走到祖先的转移方程。
fu,0=min⁡(fv,0+a,fv,0+L+a+z,fv,1+a+z)fu,1=min⁡(fv,0+L+a+z,fv,1+a+z,fv,1+a+L)f_{u,0}=\min(f_{v,0}+a,f_{v,0}+L+a+z,f_{v,1}+a+z)\\ f_{u,1}=\min(f_{v,0}+L+a+z,f_{v,1}+a+z,f_{v,1}+a+L)
注意一下啊，这里的 zz 是带符号的，也就是顺水的话为负号，否则为正号。
你可能会不知道这两个转移是为什么：
fu,0=fv,0+L+a+zfu,1=fv,1+a+Lf_{u,0}=f_{v,0}+L+a+z\\ f_{u,1}=f_{v,1}+a+L
这是很反生活常识的，第一个是你可以在陆地上的时候造船，然后再坐船过去，再丢掉船，第二个是你可以在水上的时候可以丢掉船，先走路再造船。
于是你就写出了普通转移，那么熟知矩阵乘法的你就知道，这里要使用广义矩阵乘法和动态 dp 来写了。
简单介绍一下动态 dp，对于需要多次跑 dp 的题目，且复杂度不支持跑多次，并且是递推转移的情况。那么对于这道题来说，你可以把每次的转移矩阵记下来，然后写一个数据结构支持查询区间的转移矩阵乘积即可。
那么接下来的我们就可以书写转移矩阵了。
[min⁡(a,L+a+z)a+zL+a+zmin⁡(a+z,a+L)]×[fv,0fv,1]=[fu,0fu,1]\left[ \begin{array}{l} \min(a,L+a+z) & a+z\\ L+a+z & \min(a+z,a+L) \end{array} \right] \times \left[ \begin{array}{l} f_{v,0}\\ f_{v,1} \end{array} \right] = \left[ \begin{array}{l} f_{u,0}\\ f_{u,1} \end{array} \right]
这样，我们就处理完了从儿子到祖先的 dp。接下来就是从祖先到儿子的。
注意到两者的本质是相同的，对于固定的 u,vu,v 来说，后者走过的边全是前者走过的边，只不过 zz 值变成相反数了，然后转移顺序变成了从上到下。
欸，这个从上到下不就是我们第一个矩阵转移的反方向吗，那我们对 zz 的相反值求个逆序矩阵不就是从祖先到儿子的答案了吗？
直接上树剖线段树维护树上路径的值即可。于是本题思路到此为止。

细节

感觉动态 dp 的细节都很多。比如此题你将对应的值存入初始矩阵就比较麻烦，容易存反符号。
然后就是实现树剖线段树维护矩阵的时候，注意两个矩阵的顺序是不同的，所以在 push_up 和 query 的时候，答案的合并是不同的。
并且相对于普通的树剖线段树来说，这道题目是边权并非点权，于是我们只能将父亲到自己边的权值存在当前点中。那么在求答案的过程中，我们就不能取两个点 lca⁡\operatorname{lca} 的点权值。
然后因为顺序问题，我分别写了两个函数求两种类型的贡献值，注意初始时 f0=0,f1=Lf_0=0,f_1=L。

CODE

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...