Problem#
In the year $2044$, humanity entered the cosmic era.
Country L has $n$ planets and $n-1$ bidirectional routes, each route established between two planets, and these $n-1$ routes connect all the planets of Country L.
Little P manages a logistics company that has many transportation plans, each of the form: a logistics spaceship needs to travel from planet $u_i$ to planet $v_i$ along the fastest space route. Obviously, it takes time for the spaceship to traverse a route; for route $j$, any spaceship takes time $t_j$ to traverse it, and there will be no interference between any two spaceships.
To encourage technological innovation, the king of Country L agreed to allow Little P's logistics company to participate in the construction of routes in Country L, specifically allowing Little P to transform a certain route into a wormhole, where traversing the wormhole takes no time.
Before the construction of the wormhole is completed, Little P's logistics company has pre-accepted $m$ transportation plans. After the wormhole is completed, these $m$ transportation plans will start simultaneously, with all spaceships departing together. When all $m$ transportation plans are completed, Little P's logistics company's phase of work will be finished.
If Little P can freely choose which route to transform into a wormhole, what is the shortest time required for Little P's logistics company to complete the phase of work?
For $100%$ of the data, it is guaranteed that: $1 \leq a_i,b_i \leq n$, $0 \leq t_i \leq 1000$, $1 \leq u_i,v_i \leq n$.
Solution#
First, extract the requirements of the problem—minimizing the maximum value suggests binary searching the maximum value.
Consider how to determine the validity after binary searching.
Select all paths that exceed the maximum value and mark them on the tree.
If there is an edge that is included in all selected paths, and the longest path among them minus the edge weight is less than the binary value, then it is valid; otherwise, it is not.
Implementation Issues#
Select all paths that exceed the maximum value.
The path length can be calculated using prefix sums on the tree.
Select all paths that exceed the maximum value and mark them on the tree.
Differential on the tree.
Issues Encountered
- Binary search written incorrectly.
- Need to use upper_bound.
- Binary search tests not fully initialized.
AC Code#
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 100;
int head[N], nxt[N << 1], edge[N << 1], to[N << 1], cnt = 1;
int point_to_edge[N];
int n, m;
int longest_path;
struct U
{
int m, n, length;
bool operator < (const U o) const
{
return length < o.length;
}
} u[N];
// <lca>
int anc[N][21], depth[N];
void lca_init()
{
for(int j = 1; j <= 20;j++)
{
for(int i = 1;i <= n;i++)
{
anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
}
}
int lca_query(int x, int y)
{
if(depth[x] < depth[y])
swap(x, y);
for(int j = 20;j >= 0;j--)
{
if(depth[anc[x][j]] >= depth[y])
{
x = anc[x][j];
}
}
if(x == y) return x;
for(int j = 20;j >= 0;j--)
{
if(anc[x][j] != anc[y][j])
{
x = anc[x][j], y = anc[y][j];
}
}
return anc[x][0];
}
// </lca>
// <Prefix Sum + LCA Preprocessing>
int sum[N];
void dfs_sum(int u, int fa)
{
depth[u] = depth[fa] + 1;
anc[u][0] = fa;
for(int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if(v == fa) continue;
point_to_edge[v] = i;
sum[v] = sum[u] + edge[i];
dfs_sum(v, u);
}
}
// </Prefix Sum Preprocessing>
// <Fast Input>
int read()
{
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
// </Fast Input>
void add(int x, int y, int z)
{
to[++cnt] = y;
edge[cnt] = z;
nxt[cnt] = head[x];
head[x] = cnt;
}
// <Check>
// <Tree Differential>
int differ[N], sum_differ[N];
int best_can_edge_quan = 0;
void dfs_differ(int u, int fa, int T)
{
sum_differ[u] += differ[u];
for(int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if(v == fa) continue;
dfs_differ(v, u, T);
sum_differ[u] += sum_differ[v];
}
if(sum_differ[u] == (m - T + 1) && best_can_edge_quan < edge[point_to_edge[u]])
{
best_can_edge_quan = edge[point_to_edge[u]];
}
}
// </Tree Differential>
bool check(int T)
{
best_can_edge_quan = 0;
memset(differ, 0, sizeof(differ));
memset(sum_differ, 0, sizeof(sum_differ));
U temp;
temp.m = temp.n = 0;
temp.length = T;
int first_bad_order = upper_bound(u + 1, u + 1 + m/*!!!*/, temp) - u;
if(temp.length >= u[first_bad_order].length && first_bad_order == m) return 1;
for(int i = first_bad_order;i <= m;i++)
{
differ[u[i].m]++, differ[u[i].n]++, differ[lca_query(u[i].n, u[i].m)] -= 2;
}
dfs_differ(1, 0, first_bad_order);
if(longest_path - best_can_edge_quan <= T)
{
return 1;
}
return 0;
}
// </Check>
int binary_search(int r)
{
int l = 0;
while(l < r)
{
int mid = (l + r) >> 1;
if(check(mid)/*Feasible*/)
{
r = mid;
}
else
{
l = mid + 1;
}
}
return l;
}
int main()
{
n = read(), m = read();
int x, y, z;
for(int i = 1;i <= n - 1;i++)
{
x = read(), y = read(), z = read();
add(x, y, z), add(y, x, z);
}
dfs_sum(1, 0);
lca_init();
for(int i = 1;i <= m;i++)
{
u[i].m = read(), u[i].n = read(), u[i].length = sum[u[i].n] + sum[u[i].m] - 2 * sum[lca_query(u[i].n, u[i].m)];
longest_path = max(longest_path, u[i].length);
}
sort(u + 1, u + 1 + m);
printf("%d\n", binary_search(longest_path));
return 0;
}
Actually, the tree differential combined with the tree prefix sum can be optimized without recursion.