Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Trying to DP over all states is a quadratic swamp. Look for a way to compress the graph: from each vertex, the most dangerous outgoing edge is the one with the largest endpoint.
Let be the largest endpoint of any outgoing edge from ; initially , then update with extra edges. The edges form a rooted tree if you root it at .
The non-crossing condition is doing real work: every real move in the original graph decreases the depth in this tree by at most . The edge decreases it by exactly .
For a pair , Jerry can force Tom to climb from up to in this tree. The value is
Now the problem is just summing that formula. Process vertices by decreasing depth; active vertices are possible . Activating adds to every non-root ancestor of , so querying the root path of gives over active .
Define as the farthest endpoint reachable from vertex in one move. So by default, and every extra edge updates .
Keep only the edges . Since , these edges form a rooted tree with root . Let be the depth of in this tree, with .
The key fact is that this tree is the real board. Numeric position is a bit of a bait; tree depth is what matters.
Consider an original edge . If , then in the tree this moves from to its parent, so the depth decreases by exactly .
Otherwise . Because of the non-crossing condition, no vertex inside the interval can have its farthest edge jump outside u \to p_up_uvp_u$, meaning
So every legal move in the original graph decreases tree depth by at most , and the farthest edge is the greedy move that decreases it by exactly .
Now fix starting vertices . Let
If , Jerry can simply keep taking farthest edges. After each turn Jerry is still strictly closer to the root than Tom can possibly be, because Tom can reduce depth by at most per actual move. Tom cannot force a catch, so the contribution is .
Assume . Jerry can again take farthest edges. His route is the ancestor chain from upward. Tom starts at . The two ancestor chains first meet at , so Tom cannot meet Jerry before reaching . Since Tom can reduce depth by at most per move, Jerry can force at least
Tom moves.
Tom can match this bound. His strategy is simple: after Jerry moves, if Jerry lands on Tom, stay and win. Otherwise, whenever Jerry's new depth becomes smaller than Tom's current depth, Tom moves along his own farthest edge, i.e. to his tree parent. Since Jerry's move can drop depth by at most , this is always enough to keep up. Tom climbs from toward , and Jerry cannot pass out of the relevant subtree without landing on the shared ancestor gate. Tom catches no later than .
Thus
The pair would contribute , so we can include it while summing. Nice little freebie.
Now sum the formula efficiently:
Process depths from deepest to root. When processing depth , the active set contains exactly the vertices with .
For a fixed at depth :
So we need dynamic queries of over active .
Use this identity: is the number of non-root common ancestors of and . When activating , add to every non-root vertex on the root-to- path. Then querying the sum on the root-to- path counts exactly the non-root common ancestors with every active , hence returns
This is standard heavy-light decomposition with a Fenwick tree supporting range add and range sum. Activate all vertices of the current depth before querying that depth, so equal-depth ordered pairs are counted both ways. The self-pair contributes , so no special case is needed.
Complexity is per test case, with total . Memory is .
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Fenwick {
int n = 0;
vector<ll> b1, b2;
Fenwick(int n = 0) { init(n); }
void init(int n_) {
n = n_;
b1.assign(n + 2, 0);
b2.assign(n + 2, 0);
}
void add(vector<ll>& b, int i, ll v) {
for (; i <= n; i += i & -i) b[i] += v;
}
ll sum(const vector<ll>& b, int i) const {
ll res = 0;
for (; i > 0; i -= i & -i) res += b[i];
return res;
}
void rangeAdd(int l, int r, ll v) {
if (l > r) return;
add(b1, l, v);
add(b1, r + 1, -v);
add(b2, l, v * (l - 1));
add(b2, r + 1, -v * r);
}
ll pref(int i) const {
return sum(b1, i) * i - sum(b2, i);
}
ll rangeSum(int l, int r) const {
if (l > r) return 0;
return pref(r) - pref(l - 1);
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<int> parent(n + 1, 0);
for (int i = 1; i < n; i++) parent[i] = i + 1;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
parent[u] = max(parent[u], v);
}
vector<vector<int>> child(n + 1);
for (int i = 1; i < n; i++) child[parent[i]].push_back(i);
vector<int> depth(n + 1, 0), order;
order.reserve(n);
order.push_back(n);
for (int i = 0; i < (int)order.size(); i++) {
int u = order[i];
for (int v : child[u]) {
depth[v] = depth[u] + 1;
order.push_back(v);
}
}
vector<int> sz(n + 1, 1), heavy(n + 1, 0);
int maxDepth = 0;
for (int v = 1; v <= n; v++) maxDepth = max(maxDepth, depth[v]);
for (int i = n - 1; i >= 0; i--) {
int u = order[i];
sz[u] = 1;
for (int v : child[u]) {
sz[u] += sz[v];
if (heavy[u] == 0 || sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}
vector<int> head(n + 1), pos(n + 1);
int timer = 0;
vector<pair<int, int>> st;
st.push_back({n, n});
while (!st.empty()) {
auto [start, h] = st.back();
st.pop_back();
for (int u = start; u != 0; u = heavy[u]) {
head[u] = h;
pos[u] = ++timer;
for (int v : child[u]) {
if (v != heavy[u]) st.push_back({v, v});
}
}
}
Fenwick bit(n);
auto pathAdd = [&](int v) {
while (head[v] != head[n]) {
bit.rangeAdd(pos[head[v]], pos[v], 1);
v = parent[head[v]];
}
bit.rangeAdd(pos[n] + 1, pos[v], 1);
};
auto pathQuery = [&](int v) {
ll res = 0;
while (head[v] != head[n]) {
res += bit.rangeSum(pos[head[v]], pos[v]);
v = parent[head[v]];
}
res += bit.rangeSum(pos[n] + 1, pos[v]);
return res;
};
vector<vector<int>> bucket(maxDepth + 1);
for (int v = 1; v <= n; v++) bucket[depth[v]].push_back(v);
ll ans = 0;
ll active = 0;
for (int d = maxDepth; d >= 0; d--) {
for (int v : bucket[d]) {
pathAdd(v);
active++;
}
for (int v : bucket[d]) {
ans += 1LL * d * active - pathQuery(v);
}
}
cout << ans << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Fenwick {
int n = 0;
vector<ll> b1, b2;
Fenwick(int n = 0) { init(n); }
void init(int n_) {
n = n_;
b1.assign(n + 2, 0);
b2.assign(n + 2, 0);
}
void add(vector<ll>& b, int i, ll v) {
for (; i <= n; i += i & -i) b[i] += v;
}
ll sum(const vector<ll>& b, int i) const {
ll res = 0;
for (; i > 0; i -= i & -i) res += b[i];
return res;
}
void rangeAdd(int l, int r, ll v) {
if (l > r) return;
add(b1, l, v);
add(b1, r + 1, -v);
add(b2, l, v * (l - 1));
add(b2, r + 1, -v * r);
}
ll pref(int i) const {
return sum(b1, i) * i - sum(b2, i);
}
ll rangeSum(int l, int r) const {
if (l > r) return 0;
return pref(r) - pref(l - 1);
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<int> parent(n + 1, 0);
for (int i = 1; i < n; i++) parent[i] = i + 1;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
parent[u] = max(parent[u], v);
}
vector<vector<int>> child(n + 1);
for (int i = 1; i < n; i++) child[parent[i]].push_back(i);
vector<int> depth(n + 1, 0), order;
order.reserve(n);
order.push_back(n);
for (int i = 0; i < (int)order.size(); i++) {
int u = order[i];
for (int v : child[u]) {
depth[v] = depth[u] + 1;
order.push_back(v);
}
}
vector<int> sz(n + 1, 1), heavy(n + 1, 0);
int maxDepth = 0;
for (int v = 1; v <= n; v++) maxDepth = max(maxDepth, depth[v]);
for (int i = n - 1; i >= 0; i--) {
int u = order[i];
sz[u] = 1;
for (int v : child[u]) {
sz[u] += sz[v];
if (heavy[u] == 0 || sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}
vector<int> head(n + 1), pos(n + 1);
int timer = 0;
vector<pair<int, int>> st;
st.push_back({n, n});
while (!st.empty()) {
auto [start, h] = st.back();
st.pop_back();
for (int u = start; u != 0; u = heavy[u]) {
head[u] = h;
pos[u] = ++timer;
for (int v : child[u]) {
if (v != heavy[u]) st.push_back({v, v});
}
}
}
Fenwick bit(n);
auto pathAdd = [&](int v) {
while (head[v] != head[n]) {
bit.rangeAdd(pos[head[v]], pos[v], 1);
v = parent[head[v]];
}
bit.rangeAdd(pos[n] + 1, pos[v], 1);
};
auto pathQuery = [&](int v) {
ll res = 0;
while (head[v] != head[n]) {
res += bit.rangeSum(pos[head[v]], pos[v]);
v = parent[head[v]];
}
res += bit.rangeSum(pos[n] + 1, pos[v]);
return res;
};
vector<vector<int>> bucket(maxDepth + 1);
for (int v = 1; v <= n; v++) bucket[depth[v]].push_back(v);
ll ans = 0;
ll active = 0;
for (int d = maxDepth; d >= 0; d--) {
for (int v : bucket[d]) {
pathAdd(v);
active++;
}
for (int v : bucket[d]) {
ans += 1LL * d * active - pathQuery(v);
}
}
cout << ans << '\n';
}
}