#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define dep(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define srep(i,a,b,c) for(int i=a,i##_end_=b;i<=i##_end_;i+=c)
#define sdep(i,a,b,c) for(int i=a,i##_end_=b;i>=i##_end_;i-=c)
#define mem(a,b) memset(a,b,sizeof a )
#define debug(a) cerr<<#a<<' '<<a<<"___"<<endl
using namespace std;
void in(int &r) {
    static char c;
    r = 0;
    bool flag = 0;

    while (c = getchar(), !isdigit(c))
        if (c == '-')
            flag = 1;

    do
        r = (r << 1) + (r << 3) + (c ^ 48);

    while (c = getchar(), isdigit(c));

    if (flag)
        r = -r;
}
const int mn = 2670;
int n, m, t1[mn], t2[mn], f1[mn], f2[mn];
int val[mn][mn];

vector<int> s1[mn], s2[mn];
int dis1[mn], dis2[mn];
long long f[mn][mn], dp[mn][mn];
long long calc(long long v) {
    return v * v;
}
struct node {
    long long k, b;
};
bool cmp(node a, node b, node c) {
    if (b.k == c.k)
        return b.b >= c.b;

    return (long double)(b.b - a.b) * (b.k - c.k) >= (long double)(c.b - b.b) * (a.k - b.k);
}
node sta1[mn][mn], sta2[mn];
int top1[mn], top2;
long long get(node *s, int top, int &last_pos, int v) {
    if (!top)
        return -1e18;

    while (last_pos < top && s[last_pos].k * v + s[last_pos].b <= s[last_pos + 1].k * v + s[last_pos + 1].b)
        ++last_pos;

    return s[last_pos].k * v + s[last_pos].b;
}
pair<int, node> push(node *s, int &top, int &last_pos, node x) {
    pair<int, node> nw;
    nw.first = top;

    while (top > 1 && cmp(s[top - 1], s[top], x))
        --top;//fake

    //  int l=2,r=top,ans=top;
    //  while(l<=r){
    //      int mid=l+r>>1;
    //      if(cmp(s[mid-1],s[mid],x))ans=mid-1,r=mid-1;
    //      else l=mid+1;
    //  }
    //  top=ans;
    if (last_pos > top)
        last_pos = max(1, top);

    ++top;
    nw.second = s[top];
    s[top] = x;
    return nw;
}
int last_pos2;
void redfs(int x, int rt) {
    dp[rt][x] = get(sta2, top2, last_pos2, dis2[f2[x]]) + val[rt][x] - 1LL * dis2[f2[x]] * dis2[f2[x]];
    int last_pos = last_pos2;
    //f[rt][now]-dis2[now]*dis2[now]+2*dis2[now]*k
    //val[rt][x]-dis2[f2[x]]*dis2[f2[x]]
    pair<int, node> last = push(sta2, top2, last_pos2, {2 * dis2[x], f[rt][x] - 1LL * dis2[x]*dis2[x]});
    rep(i, 0, (int)s2[x].size() - 1)redfs(s2[x][i], rt);
    sta2[top2] = last.second;
    top2 = last.first;
    last_pos2 = last_pos;
}
int pos_last1[mn][mn], last_pos1[mn];
pair<int, node> last[mn][mn];
void dfs(int x) {
    rep(i, 1, m) {
        f[x][i] = get(sta1[i], top1[i], last_pos1[i], dis1[f1[x]]) - 1LL * dis1[f1[x]] * dis1[f1[x]];
        //      dp[now][i]-dis1[now]*dis1[now]+2*dis1[now]*dis1[f1[x]]
        //      -dis1[f1[x]]*dis1[f1[x]]
    }

    if (x != 1)
        last_pos2 = 1, redfs(1, x);

    rep(i, 1, m) {
        pos_last1[x][i] = last_pos1[i];
        last[x][i] = push(sta1[i], top1[i], last_pos1[i], {2 * dis1[x], dp[x][i] - 1LL * dis1[x]*dis1[x]});
    }
    rep(i, 0, (int)s1[x].size() - 1)dfs(s1[x][i]);
    rep(i, 1, m) {
        sta1[i][top1[i]] = last[x][i].second;
        top1[i] = last[x][i].first;
        last_pos1[i] = pos_last1[x][i];
    }
}
void solve() {
    rep(i, 1, n)rep(j, 1, m)f[i][j] = -1e18, dp[i][j] = -1e18;
    dp[1][1] = 0;
    rep(i, 1, m)last_pos1[i] = 1;
    dfs(1);
    long long ans = 0;
    rep(i, 1, n)rep(j, 1, m)ans = max(ans, dp[i][j]);
    cout << ans << endl;
}
bool dis_cmp1(int a, int b) {
    return dis1[a] < dis1[b];
}
bool dis_cmp2(int a, int b) {
    return dis2[a] < dis2[b];
}
int main() {
    in(n), in(m);
    rep(i, 2, n)in(t1[i]), dis1[i] = t1[i];
    rep(i, 2, m)in(t2[i]), dis2[i] = t2[i];
    rep(i, 2, n)in(f1[i]), s1[f1[i]].push_back(i), dis1[i] += dis1[f1[i]];
    rep(i, 2, m)in(f2[i]), s2[f2[i]].push_back(i), dis2[i] += dis2[f2[i]];
    rep(i, 2, n)rep(j, 2, m)in(val[i][j]);
    rep(i, 1, n)sort(s1[i].begin(), s1[i].end(), dis_cmp1);
    rep(i, 1, m)sort(s2[i].begin(), s2[i].end(), dis_cmp2);
    solve();
    return 0;
}

亲密任务配对问题题解

题目分析

本题中，A和B各有一个任务集合，任务依赖关系构成以任务1为根的外向树。需从两人的任务树中各选一条路径（均从任务1开始，后一任务依赖前一任务），使得两条路径长度相同。每对对应任务$(a_i, b_i)$可获得亲密度$C_{a_i,b_i}$，但两人在非共同执行任务的时间段内会有亲密度惩罚（惩罚值为各自孤独执行时间的平方）。目标是最大化总亲密度（得分总和减去惩罚总和）。

动态规划模型

状态定义

设$dp[x][y]$表示A的路径终点为任务$x$、B的路径终点为任务$y$时的最大亲密度。

转移方程

对于A的任务$x$（$x \geq 2$）和B的任务$y$（$y \geq 2$），其路径需从各自的祖先$u$（$u$是$x$的祖先，包括1）和$v$（$v$是$y$的祖先，包括1）转移而来。转移方程为：

$$dp[x][y] = C_{x,y} + \max_{\substack{u \in \text{ ancestors}(x) \\ v \in \text{ ancestors}(y)}} \left( dp[u][v] - (d_A(x) - d_A(u))^2 - (d_B(y) - d_B(v))^2 \right) $$

其中$d_A(x)$表示A从任务1到$x$的总执行时间（路径总时间），$d_B(y)$同理。

转移方程优化

直接计算上述转移方程的时间复杂度极高（$O(n^2m^2)$，$n, m$为任务数），需通过数学变形和数据结构优化。

方程变形

展开惩罚项$(d_A(x)-d_A(u))^2 + (d_B(y)-d_B(v))^2$：

$$= d_A(x)^2 - 2d_A(x)d_A(u) + d_A(u)^2 + d_B(y)^2 - 2d_B(y)d_B(v) + d_B(v)^2 $$

代入转移方程并整理：

$$dp[x][y] = C_{x,y} - d_A(x)^2 - d_B(y)^2 + \max_{\substack{u \in \text{ ancestors}(x) \\ v \in \text{ ancestors}(y)}} \left( dp[u][v] + 2d_A(x)d_A(u) + 2d_B(y)d_B(v) - d_A(u)^2 - d_B(v)^2 \right) $$

分离变量与凸包优化

上述最大值可分离为关于$u$和$v$的两部分：

$$\max_u \left( 2d_A(x)d_A(u) - d_A(u)^2 + \max_v \left( dp[u][v] - d_B(v)^2 + 2d_B(y)d_B(v) \right) \right) $$

• 内层$\max_v$是关于$d_B(y)$的一次函数（斜率为$2d_B(v)$，截距为$dp[u][v] - d_B(v)^2$），可用凸包维护这些直线，查询时只需根据$d_B(y)$找最大值。
• 外层$\max_u$是关于$d_A(x)$的一次函数（斜率为$2d_A(u)$，截距为$-d_A(u)^2 + \text{内层结果}$），同样可用凸包优化。

实现细节

1. 树的遍历与路径时间计算：
   预处理$d_A(x)$和$d_B(y)$，分别表示A和B从任务1到$x$/$y$的总时间（递归累加子节点与父节点时间）。

2. 凸包维护与回溯：
   对两棵树进行深度优先遍历（DFS），遍历过程中动态维护凸包（存储一次函数）。由于树的递归特性，需在遍历子节点后回溯恢复凸包状态（保存插入前的栈顶和直线，退出时还原）。

3. 斜率单调性优化：
   按路径时间$d_A(x)$和$d_B(y)$对树的子节点排序，保证插入凸包的直线斜率单调，从而用单调栈高效维护凸包（避免二分查找，直接弹出无效直线）。

代码解析

• 变量定义：

  • $d1[x], d2[y]$：A/B从任务1到$x$/$y$的总时间。
  • $s1[x], s2[y]$：任务$x$/$y$的子节点列表（按路径时间排序）。
  • $sta1, sta2$：维护凸包的栈（存储一次函数的斜率和截距）。
  • $dp[x][y]$：状态数组，存储最大亲密度。

• 核心函数：

  • dfs(x)：遍历A的任务树，对每个节点$x$，通过B的树的遍历（redfs）计算$dp[x][y]$，并将$x$的信息插入凸包。
  • redfs(y, rt)：遍历B的任务树，对每个节点$y$，利用凸包查询计算$dp[rt][y]$（$rt$为A的当前节点），并将$y$的信息插入凸包。
  • push/get：维护凸包（插入直线并保持单调性）和查询最大值。

时间复杂度

每个节点在凸包中的插入和查询操作均为$O(1)$（因斜率单调），两棵树的总节点数为$n + m$，故总时间复杂度为$O(nm)$，可处理$n, m \leq 2666$的规模。

算法标签

• 动态规划（DP）
• 树DP
• 凸包优化（Convex Hull Trick）
• 单调栈优化
• 双树动态规划