CF-1077-E. Jerry and Tom（没有思路的时候，可以从特殊情况入手）（可以从分析单步最优入手，从局部最优到整体最优）（不符合单步最优的，我们直接删除）（太复杂了，就要想想是不是可以删一些东西，即边）（深度其实也只和儿子的数量有关系） · znzryb
## 题目大意
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))
$$
这个问题，有许多解决方法，不过，我们这里选择使用启发式合并。
启发式合并的关键就是，**合并过程复杂度**，**必须要依赖于轻儿子的这个子树的参数（如节点数量，深度等）**，不能够依赖于遍历重儿子。
不过，这个要求并不难，使用前缀和，搞一搞，就好了。
```cpp
// 计算答案，把轻儿子节点合并进主集合中。
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 数据：
```cpp
1
7 2
3 7
4 6
ans:20
```
## AC代码
AC
[https://codeforces.com/contest/2188/submission/361002651](https://codeforces.com/contest/2188/submission/361002651)
::: 源代码
```cpp
/**
* 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……）