問題#
西暦 $2044$ 年、人類は宇宙時代に突入しました。
L 国には $n$ 個の惑星があり、$n-1$ 本の双方向航路があります。各航路は 2 つの惑星の間に設置されており、この $n-1$ 本の航路は L 国のすべての惑星を結んでいます。
小 P は物流会社を運営しており、同社には多くの輸送計画があります。各輸送計画は次のような形をしています：ある物流宇宙船が $u_i$ 番の惑星から $v_i$ 番の惑星へ最速の宇宙航路で飛行する必要があります。明らかに、宇宙船が航路を通過するには時間がかかります。航路 $j$ に対して、任意の宇宙船がそれを通過するのにかかる時間は $t_j$ であり、任意の 2 隻の宇宙船の間には干渉が発生しません。
技術革新を奨励するために、L 国の国王は小 P の物流会社が L 国の航路建設に参加することを許可しました。つまり、小 P は特定の航路をワームホールに改造することができ、宇宙船がワームホールを通過する際には時間を消費しません。
ワームホールの建設が完了する前に、小 P の物流会社は $m$ 個の輸送計画を事前に受け付けました。ワームホールの建設が完了した後、これらの $m$ 個の輸送計画は同時に開始され、すべての宇宙船が一斉に出発します。これらの $m$ 個の輸送計画がすべて完了すると、小 P の物流会社の段階的な作業が完了します。
小 P がどの航路をワームホールに改造するかを自由に選択できる場合、小 P の物流会社が段階的な作業を完了するために必要な最短時間はどれくらいですか？
$100%$ のデータに対して、保証：$1 \leq a_i,b_i \leq n$、$0 \leq t_i \leq 1000$、$1 \leq u_i,v_i \leq n$。
解答#
まず問題の要求を抽出します —— 最大値を最小化することを考え、二分探索を思いつきます。
二分探索の後、どのように合法性を判断するかを考えます。
最大値を超える経路をすべて選び、木の上にマークします。
選ばれたすべての経路に含まれる辺が 1 つあり、その中で最長の経路から辺の重みを引いた値が二分値より小さい場合は合法、それ以外は不合法です。
実装の問題#
最大値を超える経路をすべて選びます。
経路の長さは木の上の前方和を使って計算できます。
最大値を超える経路をすべて選び、木の上にマークします。
木の上の差分を使用します。
発生した問題
- 二分探索の実装ミス
- upper_bound を使用する必要があります
- 二分探索のテストがすべて初期化されていない
AC コード#
#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>
// <前処理前方和+lca>
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);
}
}
// </前処理前方和>
// <高速入力>
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;
}
// </高速入力>
void add(int x, int y, int z)
{
to[++cnt] = y;
edge[cnt] = z;
nxt[cnt] = head[x];
head[x] = cnt;
}
// <チェック>
// <木の上の差分>
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]];
}
}
// </木の上の差分>
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;
}
// </チェック>
int binary_search(int r)
{
int l = 0;
while(l < r)
{
int mid = (l + r) >> 1;
if(check(mid)/*可行*/)
{
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;
}
実際には、木の上の差分と木の上の前方和は最適化でき、再帰を使用する必要はありません。