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

· · 题解

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