CF-1077-E. Jerry and Tom（没有思路的时候，可以从特殊情况入手）（可以从分析单步最优入手，从局部最优到整体最优）（不符合单步最优的，我们直接删除）（太复杂了，就要想想是不是可以删一些东西，即边）（深度其实也只和儿子的数量有关系）

题目大意

Jerry和Tom正在一个有$n$个顶点的有向图$G$上玩一个游戏，顶点编号从$1$到$n$。对于每个顶点$1 \le u < n$，从$u$到$u+1$有一条有向边。此外，还有$m$条额外的有向边。第$i$条额外边从$u_i$到$v_i$。

图$G$具有以下特殊性质：不存在两条有向边$(u_i\to v_i)$和$(u_j\to v_j)$使得$u_i < u_j < v_i < v_j$。

在游戏开始时，Jerry和Tom分别站在顶点$x$和$y$上，其中$x \ne y$。游戏按照轮次进行。在每个轮次中，玩家根据以下规则行动，Jerry先行，然后是Tom：

• Jerry 必须选择从他当前顶点出发的一条出边****并沿着它移动到终点。如果他当前顶点没有出边，则他保持原地。

• Tom 可以选择从他当前顶点出发的一条出边并沿着它移动到终点，或者选择不移动并保持原地。

如果在任何轮次结束时，Jerry和Tom在同一个顶点上（包括在顶点$n$处），游戏立即结束且Tom获胜。否则，如果Jerry最初在顶点$n$，或在任何轮次结束时到达顶点$n$，Jerry获胜。

注意，如果在一轮之后，Jerry和Tom都在顶点$n$，则Tom获胜。

在整个游戏过程中，两个玩家都知道对方的位置。

可以证明游戏会在有限轮次内结束。

对于一对整数$1 \le x,y \le n$，$x \ne y$，定义$f(x,y)$如下：

• Jerry和Tom将进行一个游戏，其中Jerry从顶点$x$开始，Tom从顶点$y$开始。Tom想赢，但他也想最小化他实际移动的次数（即，他改变顶点的轮次数；原地不算移动）。假设双方都以最佳方式行动，如果Tom不能赢则令$f(x,y)=0$；否则，令$f(x,y)$为Tom强迫赢所需的最小移动次数。如果Tom在最佳游戏中获胜，Jerry仍会尽力最大化Tom必须移动的次数。

计算

$$\sum\limits_{1 \le x,y \le n, x \ne y}f(x,y).$$

思路讲解

我们梳理一下题意，并进行一下样例解释

题目不允许这样子的两条边存在。

在样例 2 中，贡献为 1 的两种情况。

如果说没有额外的边，那么答案就是 $0$。因为 Tom 在 Jerry 前面，反正肯定赢不了。Tom 在 Jerry 后面，守株待兔即可。可以发现，无论什么情况，根据定义，都是 $0$。

我们现在这个问题还是回来，什么时候肯定不会有这个追及，有这个贡献？其实就是如果把额外边当作区间加法的话，Tom 在没有被任何区间覆盖的地方，肯定是不会有答案贡献的。

不过我们发现，这样子一种一种情况看，实在是太慢了。既然是博弈题目，那么Tom 和 Jerry 的最优策略是什么呢？就是每步都走最远的边。

因此，我们不妨把 Tom 走的路径，以及 Jerry 走的路径绘画在一张图上（按照上面说的最优策略），这张图，其实是一颗树。

或者，换句话说，我们只保留每个点的最长出边（这样子就可以形成一颗树），较短的出边，我们直接删除（因为不符合）。

接着就是来处理这个贡献与计算问题了。

我们想要计算的就是，当我们已经知道 一个点 $u$，在其他所有树上，比他的深度浅或者同样深度的所有点，记作 $V$ 集合，贡献为：

$$\sum_{v\in V}\text{dep}(u)-\text{dep}(\text{lca}(u,v))$$

这个问题，有许多解决方法，不过，我们这里选择使用启发式合并。

启发式合并的关键就是，合并过程复杂度，必须要依赖于轻儿子的这个子树的参数（如节点数量，深度等），不能够依赖于遍历重儿子。

不过，这个要求并不难，使用前缀和，搞一搞，就好了。

// 计算答案，把轻儿子节点合并进主集合中。
for (auto [dep_son,cnt]:node_dep_cnt_mtx[to]) {
    // cnt 是深度为 dep_son，较大的节点的数量（Jerry），get_presum_val 拿到的
    // 是所有比 dep_son 小的点的 dep(v)-dep(lca(u,v)) 的这个和
    ans+=cnt*get_presum_val(dep_son);
    // 深度相同的节点可以反复贡献（可以理解为上面也可以贡献，下面也可以贡献）
    ans+=cnt*node_dep_cnt_mtx[u][dep_son]*(dep_son-dep);
    // 这个是深度比 dep_son 大的节点的数量
    ll num_gt_dep=sum_node-get_presum_num(dep_son);
    // 深度比 dep 深度深的节点，也会贡献，因为已经在重儿子中的深度深的节点
    // 合并进来的时候还没有这样一个节点，贡献的就是 dep_son-dep(lca)
    ans+=num_gt_dep*cnt*(dep_son-dep);
    // 这里是顺手进行一个更新
    node_dep_cnt_mtx[u][dep_son]+=cnt;
}

注意这个有可能出现重儿子比轻儿子的这个链长短的这个情况（当然可以变为分长儿子/短儿子）。这个时候直接取这个前缀和，因为我们用 map 实现，就会取到 $0$。这个时候可以用一个匿名 get 函数特判一下这个情况。

这种情况的一个 hack 数据：

1
7 2
3 7
4 6

ans:20

AC代码

AC
https://codeforces.com/contest/2188/submission/361002651

源代码

/**
 * Problem: E. Jerry and Tom
 * Contest: Codeforces Round 1077 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2188/problem/E
 * Created: 2026-01-30 16:36:38
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */
#include <bits/stdc++.h>

#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *我们现在就是卡在这个追及问题。
 *
 *现在我们卡在这个就是非对称贡献问题。
 *就是，我们卡在这个
 *
 */

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<ll> diff_ls(N + 2);
    vector<ll> parent(N + 2);
    for (int i = 1; i <= N - 1; ++i) {
        parent[i] = i + 1;
    }
    for (int i = 1; i <= M; ++i) {
        ll u, v;
        cin >> u >> v;
        parent[u] = max(parent[u], v);
    }
    vector<vector<ll> > g(N + 2);
    for (int i = 1; i <= N - 1; ++i) {
        g[i].push_back(parent[i]);
        g[parent[i]].push_back(i);
    }
    vector<ll> size_ls(N + 2, 1), heavy_son(N + 2), mx_dep_ls(N+2);


    auto dfs1 = [&](auto &&self, ll u, ll p) -> ll {
        for (auto to: g[u]) {
            if (to == p) {
                continue;
            }
            size_ls[u] += self(self, to, u);
            if (size_ls[to] >= size_ls[heavy_son[u]]) {
                heavy_son[u] = to;
            }
        }
        return size_ls[u];
    };
    dfs1(dfs1, N, -1);
    // 我们想要计算的就是，当我们已经知道 一个点 v，在其他
    // 所有树上，比他的深度浅或者同样深度的所有点，贡献 dep(u)-dep(lca(u,v))
    // 不过只有其他

    // dsu on tree
    vector<map<ll,ll> > node_dep_cnt_mtx(N + 2);
    ll ans=0;
    auto dfs2 = [&](auto &&self, ll u, ll p,ll dep) -> void {
        for (auto to: g[u]) {
            if (to == p) continue;
            if (to != heavy_son[u]) continue;
            self(self, to, u, dep+1);
            // 复用重儿子的空间，避免 mle。
            swap(node_dep_cnt_mtx[u], node_dep_cnt_mtx[to]);
            break;
        }
        ll sum_node=size_ls[heavy_son[u]];
        for (auto to: g[u]) {
            if (to == p) continue;
            if (to == heavy_son[u]) continue;
            // 我们先写的 naive 一点
            self(self,to,u,dep+1);
            // 其实只要我们合并的方法只和轻儿子的子树相关性质有关系
            // 比如说深度，
            ll mx_dep=node_dep_cnt_mtx[to].rbegin()->first;
            // 虽然说比他的深度浅或者同样深度的所有点，贡献 dep(u)-dep(lca(u,v))
            // 但比他深度深的节点，也会贡献，因为已经在重儿子中的深度深的节点
            // 合并进来的时候还没有这样一个节点，贡献的就是 dep(v)-dep(lca(u,v))

            // 算前缀和
            map<ll,ll> pre_sum_val_mp,pre_sum_num_mp;
            ll lsum=0,lsum_node=0;
            for (auto [dep_son,cnt]:node_dep_cnt_mtx[u]) {
                // 像这里，我虽然遍历了重儿子的这个 node，但是实际上
                // 这里遍历的复杂度取决于轻儿子的这个最大深度
                if (dep_son>mx_dep) {
                    break;
                }
                lsum+=cnt*(dep_son-dep);
                lsum_node+=cnt;
                pre_sum_val_mp[dep_son]=lsum;
                pre_sum_num_mp[dep_son]=lsum_node;
            }
            auto get_presum_val=[&](ll dep_son) -> ll {
                if (pre_sum_val_mp.contains(dep_son)) {
                    return pre_sum_val_mp[dep_son];
                }else {
                    return pre_sum_val_mp.rbegin()->second;
                }
            };
            auto get_presum_num=[&](ll dep_son) -> ll {
                if (pre_sum_num_mp.contains(dep_son)) {
                    return pre_sum_num_mp[dep_son];
                }else {
                    return pre_sum_num_mp.rbegin()->second;
                }
            };
            // 计算答案，把轻儿子节点合并进主集合中。
            for (auto [dep_son,cnt]:node_dep_cnt_mtx[to]) {
                // cnt 是深度为 dep_son，较大的节点的数量（Jerry），get_presum_val 拿到的
                // 是所有比 dep_son 小的点的 dep(v)-dep(lca(u,v)) 的这个和
                ans+=cnt*get_presum_val(dep_son);
                // 深度相同的节点可以反复贡献（可以理解为上面也可以贡献，下面也可以贡献）
                ans+=cnt*node_dep_cnt_mtx[u][dep_son]*(dep_son-dep);
                // 这个是深度比 dep_son 大的节点的数量
                ll num_gt_dep=sum_node-get_presum_num(dep_son);
                // 深度比 dep 深度深的节点，也会贡献，因为已经在重儿子中的深度深的节点
                // 合并进来的时候还没有这样一个节点，贡献的就是 dep_son-dep(lca)
                ans+=num_gt_dep*cnt*(dep_son-dep);
                // 这里是顺手进行一个更新
                node_dep_cnt_mtx[u][dep_son]+=cnt;
            }
            sum_node+=size_ls[to];
        }
        node_dep_cnt_mtx[u][dep]++;
    };
    dfs2(dfs2,N,-1,1);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    while (lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2188/submission/361002651

1
3 1
1 3

1
5 1
1 4

1
7 2
3 7
4 6

20
*/

心路历程（WA，TLE，MLE……）