PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sushil2006
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy - Medium
PREREQUISITES:
Path min/max queries
PROBLEM:
You’re given a tree with N vertices.
The cost of moving from u to v equals the product of the minimum and maximum labels on the path from u to v.
Starting from S, find the minimum cost of reaching every other vertex.
EXPLANATION:
First, observe that we never need to consider costs that are very large.
In particular, to move S\to x we can always do S\to 1 and 1\to x, for a total cost of at most 2N (since the minimum on each of those jumps is 1.)
So, any paths with cost \gt 2N are certainly useless.
Next, for a fixed endpoint, let’s look at an optimal path from S to x.
Suppose this optimal path is S = v_1 \to v_2 \to v_3 \to\ldots \to v_k = x.
We make a few observations about what the structure of such a path must look like.
Claim 1: v_i does not lie on the path between v_{i-1} and v_{i+1}.
Proof
Simple algebra, use the fact that for any positive values a, b, x, y we have
a\cdot x + b\cdot y \gt \min(a, b) \cdot \max(x, y)This means that if v_i lies on the path between them, v_{i-1} \to v_{i+1} is always lower cost than having to go through v_i.
Claim 2: There exists an optimal solution where for every i, v_i is the minimum label either on the v_{i-1} \to v_i path, or the v_{i}\to v_{i+1} path.
Proof
From our first claim, v_i doesn’t lie on the path between v_{i-1} and v_{i+1}.
If v_i isn’t the minimum on either path, we can instead replace v_i with the vertex one step closer to the (v_{i-1}, v_{i+1}) path.
This doesn’t change the minimum on either path, but might decrease the maximums; so the overall cost isn’t worse.
This replacement can be repeated till v_i is the minimum of one of the paths (or till v_i lies on the (v_{i-1}, v_{i+1}) path, but that would contradict optimality).Starting with an arbitrary optimal sequence, we can thus adjust v_2, v_3, \ldots, v_{k-1} in order, proving our claim.
This second claim is useful, because it allows us to greatly reduce the scope of moves that need to be considered.
In particular, we have the following.
Claim 3: Suppose v_i = \text{pathmin}(v_i, v_{i+1}) for some 1 \lt i \lt k.
Then, in an optimal solution, i = k-1 must hold.Proof
The crux of the argument here is the fact that if v_i = \text{pathmin}(v_i, v_{i+1}), then v_j = \text{pathmin}(v_j, v_{j+1}) for every i\leq j \lt k.
This can be proved inductively: it’s true for j = i by assumption, and if it’s true for j, it must be true for j+1 as well: since v_{j+1} \neq \text{pathmin}(v_j, v_{j+1}), by claim 2 we must have
v_{j+1} = \text{pathmin}(v_{j+1}, v_{j+2}).Now, note that moving from v_i to v_k along a set of paths means that we’ll have visited a connected subset of vertices.
Further, as a result of our previous observation, the minimum label within this connected subset is exactly v_i.Let M be the maximum label within this connected subset.
We’ve passed through M, which means we’ve definitely incurred a cost of at least M\cdot x for some x \geq v_i (since v_i is the minimum).
However, if we simply deleted every intermediate vertex, and directly went v_i\to v_k, we’d incur a cost of at most v_i\cdot M, which is clearly better.This proves our claim of i = k-1.
Similarly, it can be seen that if v_i = \text{pathmin}(v_i, v_{i-1}), then i = 2 is optimal.
The above claim is extremely strong, because it tells us:
Claim 4: In an optimal solution, k \leq 3, meaning we need to consider at most 2 jumps.
Proof
Suppose k \geq 4. Let’s look at v_2 and v_3.
If \text{pathmin}(v_2, v_3) = v_2, then as per claim 3 it’s optimal to just not have v_3.
Similarly, if \text{pathmin}(v_2, v_3) = v_3, it’s optimal to not have v_2.This means we only need to consider the case when \text{pathmin}(v_2, v_3) isn’t either of the endpoints.
However, in such a case, it’s optimal to just drop v_2 and go directly from v_1\to v_3 instead (apply the same connected subset argument from claim 3).This way, we can repeatedly drop vertices without making the cost worse, till we’re left with only 3.
Now, the cost of going S\to x with a single jump is easy to compute, requiring only a single path min/max query.
Let’s instead figure out what an optimal solution with two jumps might look like.
Suppose S \to y \to x is optimal to reach x.
Claim 2 tells us that either y = \text{pathmin}(S, y) or y = \text{pathmin}(y, x).
Let’s look at each case separately.
Case 1: y = \text{pathmin}(y, x)
Here, observe that we’re still bound by the constraint of not taking paths whose cost is \gt 2N.
So, if y\cdot \text{pathmax}(x, y) \gt 2N, it’s definitely not optimal to consider y\to x.
In particular, if x\cdot y \gt 2N we’ll definitely have y\cdot \text{pathmax}(x, y) \gt 2N.
This means, for a fixed y, we only need to consider x \leq \frac{2N}{y}.
Summed up across all y, there are \mathcal{O}(N\log N) such paths to consider.
For each such path (x, y), update the answer of x with \text{cost}(S, y) + \text{cost}(y, x).
Case 2: y = \text{pathmin}(S, y)
Here, if y \neq \text{pathmin}(y, x), it’s simply more optimal to move directly from S to x (to see why, replicate the last part of the proof of claim 4).
So, in an optimal solution, we must have y = \text{pathmin}(y, x) anyway, going back to the first case.
In summary, all we really need to do is compute the maximum and minimum along \mathcal{O}(N\log N) paths reasonably quickly.
This is a standard problem and can be done in various ways, ranging from \mathcal{O}(1) to \mathcal{O}(\log^2 N) time - pick your poison (make sure that either your complexity or your constant factor is low enough though!)
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
Tester's code (C++)
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T>
struct RMQ {
vector<vector<T>> jmp;
RMQ(const vector<T>& V) : jmp(1, V) {
for (int pw = 1, k = 1; pw * 2 <= (int)size(V); pw *= 2, ++k) {
jmp.emplace_back(size(V) - pw * 2 + 1);
for (int j = 0; j < (int)size(jmp[k]); ++j)
jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b) {
assert(a < b); // or return inf if a == b
int dep = 31 - __builtin_clz(b - a);
return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
}
};
struct LCA {
int T = 0;
vector<int> time, path, ret, depth;
RMQ<int> rmq;
LCA(auto& C, int root = 0) : time(size(C)), depth(size(C)), rmq((dfs(C,root,-1), ret)) {}
void dfs(auto& C, int v, int par) {
time[v] = T++;
for (int y : C[v]) if (y != par) {
depth[y] = 1 + depth[v];
path.push_back(v), ret.push_back(time[v]);
dfs(C, y, v);
}
}
int lca(int a, int b) {
if (a == b) return a;
tie(a, b) = minmax(time[a], time[b]);
return path[rmq.query(a, b)];
}
int dist(int a, int b) {
return depth[a] + depth[b] - 2*depth[lca(a,b)];
}
};
struct CentroidDecomp {
int N;
vector<basic_string<int>> adj, ctree;
vector<int> size, mark, dep;
vector<array<array<int, 2>, 18>> val;
CentroidDecomp(auto &_adj) : N(ssize(_adj)), adj(_adj), ctree(N), size(N), mark(N), dep(N), val(N) {}
void dfs_size(int u, int p = -1) {
size[u] = 1;
for (int v : adj[u]) {
if (!mark[v] and v != p) {
dfs_size(v, u);
size[u] += size[v];
}
}
}
int find_centroid(int root, int u, int p = -1) {
for (int v : adj[u]) {
if (mark[v] or v == p) continue;
if (size[v] > size[root]/2) return find_centroid(root, v, u);
}
return u;
}
int construct(int u, int level = 0) {
dfs_size(u);
int c = find_centroid(u, u);
dep[c] = level;
auto dfs = [&] (const auto &self, int v, int par = -1, int mn = INT_MAX, int mx = 0) -> void {
mn = min(mn, v+1), mx = max(mx, v+1);
val[v][level] = {mn, mx};
for (int x : adj[v]) {
if (!mark[x] and x != par) self(self, x, v, mn, mx);
}
};
dfs(dfs, c);
mark[c] = 1;
for (int v : adj[c]) if (!mark[v]) {
ctree[c].push_back(construct(v, level+1));
}
return c;
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, src; cin >> n >> src;
vector tree(n, basic_string<int>());
for (int i = 0; i < n-1; ++i) {
int u, v; cin >> u >> v;
tree[--u].push_back(--v);
tree[v].push_back(u);
}
CentroidDecomp CD(tree);
int cen = CD.construct(0);
LCA L(CD.ctree, cen);
vector<int> direct(n+1), ans(n+1);
for (int i = 1; i <= n; ++i) {
if (i == src) continue;
int l = L.lca(i-1, src-1);
int d = CD.dep[l];
int mn = min(CD.val[i-1][d][0], CD.val[src-1][d][0]);
int mx = max(CD.val[i-1][d][1], CD.val[src-1][d][1]);
if (1ll*mn*mx <= 2*n) direct[i] = mn*mx;
else direct[i] = 2*n + 1;
}
ans = direct;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= n and i*j <= 2*n; ++j) {
int l = L.lca(i-1, j-1);
int d = CD.dep[l];
int mn = min(CD.val[i-1][d][0], CD.val[j-1][d][0]);
int mx = max(CD.val[i-1][d][1], CD.val[j-1][d][1]);
ans[i] = min(ans[i], direct[j] + mn*mx);
ans[j] = min(ans[j], direct[i] + mn*mx);
}
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
cout << '\n';
}
}