15011418730 LV 7 @ 2025-8-24 21:59:26

自动搬运

来自洛谷，原作者为

	Add_Catalyst 喵哇喵

搬运于2025-08-24 21:59:26，当前版本为作者最后更新于2024-10-02 09:53:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P4367 [Code+#4] Tommy 的结合题解

知识点

树形 DP（也许不是吧），带回撤的凸包，斜率优化。

题意简述

给你两棵外向树 $V_A$ 和 $V_B$ ，每个点都有一个花费 $t_i$ ，分别选出两条以根为首位的路径 ${p_A}_1^{k_A}$ 和 ${p_B}_1^{k_B}$ ，再从中选出相同数量 $m$ 的节点 ${a}_1^m$ 和 ${b}_1^m$ 按顺序一一配对，两条路径中所有没有被选中的连续点段的花费和的平方和为 $T$ ，其权值为 $T+\sum_{i=1}^m c_{a_i,b_i}$ 。

求能够达到的最大权值。

做法分析

$O(n^4)$

最基础的 DP 套路：设 $f_{u,v}$ 为在 $V_A,V_B$ 上最后选的点分别为 $u,v$ ，所得的最大值是多少，那么可以得到转移方程：（ $Pa_u$ 代表 $u$ 的祖先集合， $Pa_v$ 同理。）

$$x \in Pa_u,y \in Pa_v \\ f_{u,v} = \max{\{ f_{x,y} - (t_{fa_u}-t_x)^2 - (t_{fa_v}-t_y)^2 + c_{u,v} \}} \\ \tag{1} $$

（我们现在可以得到 7 分的高分了！！！ヾ(@^▽^@)ノ）

$O(n^3)$

考虑优化：状态割裂。

观察上式，有一部分 $f_{x,y} - (t_{fa_v} - t_y)^2$ 会被多次重复使用，那么我们把它单提出来，开一个 $g_{x,v}$ 来处理和存储。

$$x \in Pa_u,y \in Pa_v \\ g_{x,v} = \max{\{ f_{x,y} - (t_{fa_v} - t_y)^2 \}} \\ \begin{aligned} f_{u,v} & = \max{\{ f_{x,y} - (t_{fa_u}-t_x)^2 - (t_{fa_v}-t_y)^2 + c_{u,v} \}} \\ f_{u,v} & = \max{\{ [f_{x,y} - (t_{fa_v}-t_y)^2] - (t_{fa_u}-t_x)^2 + c_{u,v} \}} \\ f_{u,v} & = \max{\{ g_{x,v} - (t_{fa_u}-t_x)^2 \}} + c_{u,v} \\ \end{aligned} \tag{2} $$

$O(n^2 \log_2{n})$

看到平方，我们能想到什么？斜率优化！！！不过比较麻烦的是， $f$ 和 $g$ 的转移式中都有平方，也就是说他们都需要斜率优化。那么接下来就开始推式子：

$$y \in Pa_v \\ \begin{aligned} g_{x,v} & = \max{\{ f_{x,y} - (t_{fa_v} - t_y)^2 \}} \\ g_{x,v} & = \max{\{ 2 t_y t_{fa_v} + (f_{x,y} - t_y^2) \}} - t_{fa_v}^2 \\ \end{aligned} \tag{3} $$$$x \in Pa_u \\ \begin{aligned} f_{u,v} & = \max{\{ g_{x,v} - (t_{fa_u}-t_x)^2 \}} + c_{u,v} \\ f_{u,v} & = \max{\{ 2 t_x t_{fa_u} + (g_{x,v} - t_x^2) \}} - t_{fa_u}^2 + c_{u,v} \\ \end{aligned} \tag{4} $$

实现

现在我们有了思路，考虑如何实现。

我们先在 $V_A$ 上 DFS，当到了一个不是 1 的节点就开始在 $V_B$ 上 DFS 并做转移。对于斜率优化的部分，你可以考虑可持久化凸包（没试过，不过空间似乎足够），当然，由于我们是在树上操作，我们还可以用带回撤的凸包来解决。

注意

带回撤的凸包不能使用尺取（暴力插入或暴力查询），因为尺取基于的时间复杂度是均摊复杂度，而均摊复杂度不适用于带回撤一类的操作，所以我们在插入和查询的时候都必须用二分。

注：本题数据由于过水，插入和查询都用尺取会有更快的速度，但请不要误认为那是正解。

$O(n^2)$ （不保证正确性）

命题人在报告中写到可能可以用轻重链剖分（轻链二分，重链尺取）来优化，但我不知道怎么证明……

CODE

$O(n^4)$

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define FOR(i,a,b) for(int i(a);i<=(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(b);--i)
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i(g.h[x]),y(g[i].v);~i;y=g[i=g[i].nxt].v)
using namespace std;
constexpr int N(2.7e3+10);
int c[N][N];
ll ans;
ll f[N][N];
struct Tree {
	int n;
	struct node {
		int t,fa,pre,dep;
		vector<int> son;
	} tr[N];
	node &operator[](int i) {
		return tr[i];
	}
} A,B;
constexpr ll Pow2(const int x) {
	return 1ll*x*x;
}
int main() {
	scanf("%d%d",&A.n,&B.n);
	FOR(i,2,A.n)scanf("%d",&A[i].t);
	FOR(i,2,B.n)scanf("%d",&B[i].t);
	FOR(i,2,A.n)scanf("%d",&A[i].fa),A[A[i].fa].son.push_back(i),A[i].pre=A[A[i].fa].pre+A[i].t,A[i].dep=A[A[i].fa].dep+1;
	FOR(i,2,B.n)scanf("%d",&B[i].fa),B[B[i].fa].son.push_back(i),B[i].pre=B[B[i].fa].pre+B[i].t,B[i].dep=B[B[i].fa].dep+1;
	FOR(i,2,A.n)FOR(j,2,B.n)scanf("%d",&c[i][j]);
	RCL(f,-0x3f,f,1),f[1][1]=0;
	FOR(u,1,A.n)FOR(v,1,B.n) {
		for(int x(A[u].fa); x; x=A[x].fa)for(int y(B[v].fa); y; y=B[y].fa)
				tomax(f[u][v],(f[x][y]-Pow2(B[B[v].fa].pre-B[y].pre))-Pow2(A[A[u].fa].pre-A[x].pre)+c[u][v]);
		tomax(ans,f[u][v]);
	}
	printf("%lld",ans);
	return 0;
}

$O(n^3)$

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define FOR(i,a,b) for(int i(a);i<=(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(b);--i)
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i(g.h[x]),y(g[i].v);~i;y=g[i=g[i].nxt].v)
using namespace std;
constexpr int N(2.7e3+10);
int c[N][N];
ll ans;
ll f[N][N],g[N][N];
struct Tree {
	int n,idx;
	int dfn[N];
	struct node {
		int t,fa,dl,dr;
		vector<int> son;
	} tr[N];
	int &operator()(int i) {
		return dfn[i];
	}
	node &operator[](int i) {
		return tr[i];
	}
	void dfs(int u) {
		dfn[tr[u].dl=++idx]=u;
		for(int v:tr[u].son)dfs(v);
		tr[u].dr=idx;
	}
} A,B;
constexpr ll Pow2(const int x) {
	return 1ll*x*x;
}
int main() {
	scanf("%d%d",&A.n,&B.n);
	FOR(i,2,A.n)scanf("%d",&A[i].t);
	FOR(i,2,B.n)scanf("%d",&B[i].t);
	FOR(i,2,A.n)scanf("%d",&A[i].fa),A[A[i].fa].son.push_back(i),A[i].t+=A[A[i].fa].t;
	FOR(i,2,B.n)scanf("%d",&B[i].fa),B[B[i].fa].son.push_back(i),B[i].t+=B[B[i].fa].t;
	FOR(i,2,A.n)FOR(j,2,B.n)scanf("%d",&c[i][j]);
	RCL(f,-0x3f,f,1),RCL(g,-0x3f,g,1),f[1][1]=0,B.dfs(1);
	FOR(i,2,B.n)g[1][i]=-1ll*B[B[i].fa].t*B[B[i].fa].t;
	FOR(u,2,A.n)FOR(v,2,B.n) {
		for(int x(A[u].fa); x; x=A[x].fa)tomax(f[u][v],g[x][v]-Pow2(A[A[u].fa].t-A[x].t)+c[u][v]);
		FOR(i,B[v].dl+1,B[v].dr)tomax(g[u][B(i)],f[u][v]-Pow2(B[B[B(i)].fa].t-B[v].t));
		tomax(ans,f[u][v]);
	}
	printf("%lld\n",ans);
	return 0;
}

$O(n^2\log_2{n})$

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define FOR(i,a,b) for(int i(a);i<=(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(b);--i)
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
using namespace std;
namespace IOstream {
#define getc() getchar()
#define putc(c) putchar(c)
#define blank(c) ((c)==' '||(c)=='\n'||(c)=='\r'||(c)==(EOF))
#define isdigit(c) ('0'<=(c)&&(c)<='9')
	template<class T>inline void rd(T &x) {
		static bool sign(0);
		static char ch(0);
		for(x=0,sign=0,ch=getc(); !isdigit(ch); ch=getc())if(ch=='-')sign^=1;
		for(; isdigit(ch); x=(x<<1)+(x<<3)+(ch^'0'),ch=getc());
		return x=sign?-x:x,void();
	}
	template<class T>inline void wr(T x,char End='\n') {
		static short top(0),st[100];
		x<0?putc('-'),x=-x:0,top=0;
		do st[++top]=x%10,x/=10;
		while(x);
		for(; top; putc(st[top]^'0'),--top);
		return putc(End),void();
	}
#undef blank
#undef isdigit
} using namespace IOstream;
typedef __int128 Int;
constexpr int N(2.7e3+10);
constexpr ll LINF(1e14);
int c[N][N];
ll ans;
ll f[N][N];
struct Func {
	int k;
	ll b;
	Func(int k=0,ll b=0):k(k),b(b) {}
	ll y(const int x) {
		return (ll)k*x+b;
	}
};
struct Stack {
	int top;
	Func st[N];
	Func &operator[](int i) {
		return st[i];
	}
	Func Insert(const Func x) {
		auto cmp=[&](Func a,Func b,Func c,Func d) {
			return (Int)(a.b-b.b)*(d.k-c.k)<=(Int)(c.b-d.b)*(b.k-a.k);
		};
		for(int l(2),r(top),mid((l+r)>>1); l<=r; mid=(l+r)>>1)
			cmp(x,st[mid-1],st[mid],st[mid-1])?top=r=mid-1:l=mid+1;
		Func tmp(st[++top]);
		return st[top]=x,tmp;
	}
	ll Bound(const int x) {
		if(!top)return -LINF;
		int ans(1);
		auto cmp=[&](Func a,Func b) {
			return (a.b-b.b)<=(Int)x*(b.k-a.k);
		};
		for(int l(2),r(top),mid((l+r)>>1); l<=r; mid=(l+r)>>1)
			cmp(st[mid-1],st[mid])?ans=mid,l=mid+1:r=mid-1;
		return st[ans].y(x);
	}
} St,st[N];
struct Tree {
	int n;
	struct node {
		int t,fa;
		vector<int> son;
	} tr[N];
	node &operator[](int i) {
		return tr[i];
	}
} A,B;
void DP_B(int u,int v) {
	int top(St.top);
	ll g(st[v].Bound(A[A[u].fa].t<<1)-(ll)A[A[u].fa].t*A[A[u].fa].t);
	tomax(ans,f[u][v]=St.Bound(B[B[v].fa].t<<1)-(ll)B[B[v].fa].t*B[B[v].fa].t+c[u][v]);
	Func val(St.Insert(Func(B[v].t,g-1ll*B[v].t*B[v].t)));
	for(const int &y:B[v].son)DP_B(u,y);
	St[St.top]=val,St.top=top;
}
void DP_A(int u) {
	if(u^1)DP_B(u,1);
	vector<int> tops(B.n+1,0);
	vector<Func> vals(B.n+1,Func(0,0));
	FOR(v,1,B.n)tops[v]=st[v].top,vals[v]=st[v].Insert(Func(A[u].t,f[u][v]-1ll*A[u].t*A[u].t));
	for(const int &x:A[u].son)DP_A(x);
	FOR(v,1,B.n)st[v][st[v].top]=vals[v],st[v].top=tops[v];
	tops.clear(),vals.clear();
}
int main() {
	rd(A.n),rd(B.n);
	FOR(i,2,A.n)rd(A[i].t);
	FOR(i,2,B.n)rd(B[i].t);
	FOR(i,2,A.n)rd(A[i].fa),A[A[i].fa].son.push_back(i),A[i].t+=A[A[i].fa].t;
	FOR(i,2,B.n)rd(B[i].fa),B[B[i].fa].son.push_back(i),B[i].t+=B[B[i].fa].t;
	FOR(i,2,A.n)FOR(j,2,B.n)rd(c[i][j]);
	FOR(i,1,A.n)FOR(j,1,B.n)f[i][j]=-LINF;
	f[1][1]=0,DP_A(1),wr(ans);
	return 0;
}

ID

3337

时间

3000ms

内存

1024MiB

难度

(无)

标签

Code+

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

P4367 [Code+#4] Tommy 的结合题解

知识点

题意简述

做法分析

$O(n^4)$

$O(n^3)$

$O(n^2 \log_2{n})$

实现

注意

$O(n^2)$ （不保证正确性）

CODE

$O(n^4)$

$O(n^3)$

$O(n^2\log_2{n})$

[Code+#4] Tommy 的结合

信息

1 条题解

自动搬运

以下是正文

P4367 [Code+#4] Tommy 的结合 题解

知识点

题意简述

做法分析

O(n4)O(n^4)O(n4)

O(n3)O(n^3)O(n3)

O(n2log⁡2n)O(n^2 \log_2{n})O(n2log2​n)

实现

注意

O(n2)O(n^2)O(n2)（不保证正确性）

CODE

O(n4)O(n^4)O(n4)

O(n3)O(n^3)O(n3)

O(n2log⁡2n)O(n^2\log_2{n})O(n2log2​n)

[Code+#4] Tommy 的结合

信息

还没有账户？

登录

P4367 [Code+#4] Tommy 的结合题解

$O(n^4)$

$O(n^3)$

$O(n^2 \log_2{n})$

$O(n^2)$ （不保证正确性）

$O(n^4)$

$O(n^3)$

$O(n^2\log_2{n})$