【NOIP 2015】Day2 T3 运输计划

2023-07-26 11:22:16

Problem

Background

公元 $2044$ 年,人类进入了宇宙纪元。

Description

公元$2044$ 年，人类进入了宇宙纪元。

$L $国有 $n$ 个星球，还有 $n-1$ 条双向航道，每条航道建立在两个星球之间，这 $n-1$ 条航道连通了 $L$ 国的所有星球。

小 $P$ 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 $u_i$ 号星球沿最快的宇航路径飞行到 $v_i$ 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 $j$，任意飞船驶过它所花费的时间为 $t_j$，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， $L$ 国国王同意小 $P$ 的物流公司参与 $L$ 国的航道建设，即允许小$P$ 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 $P$ 的物流公司就预接了 $m$ 个运输计划。在虫洞建设完成后，这 $m$ 个运输计划会同时开始，所有飞船一起出发。当这 $m$ 个运输计划都完成时，小 $P$ 的物流公司的阶段性工作就完成了。

如果小 $P$ 可以*选择将哪一条航道改造成虫洞，试求出小 $P$ 的物流公司完成阶段性工作所需要的最短时间是多少？

Input Format

第一行包括两个正整数 $n, m$，表示 $L$ 国中星球的数量及小 $P$ 公司预接的运输计划的数量，星球从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行描述航道的建设情况，其中第 $i$ 行包含三个整数 $a_i, b_i$ 和 $t_i$，表示第 $i$ 条双向航道修建在 $a_i$ 与 $b_i$两个星球之间，任意飞船驶过它所花费的时间为 $t_i$。数据保证 $1 \leq a_i,b_i \leq n$ 且 $0 \leq t_i \leq 1000$。

接下来 $m$ 行描述运输计划的情况，其中第 $j$ 行包含两个正整数 $u_j$ 和 $v_j$，表示第 $j$ 个运输计划是从 $u_j$ 号星球飞往 $v_j$号星球。数据保证 $1 \leq u_i,v_i \leq n$

Output Format

一个整数，表示小 $P$ 的物流公司完成阶段性工作所需要的最短时间。

Sample

Input

Output

Range

对于 $100\%$ 的数据，$100 \leq n \leq 300000$，$1 \leq m \leq 300000$。

Algorithm

二分答案，树上乱搞

Mentality

首先看到题目所求，是求最大值最小化。一下子就发现答案是单调的，那么二分答案就确定了。那么二分之后如何$check$呢？

可以发现，当我们二分到一个值$mid$时，对于所有小于等于它的路径都无需处理。
对于所有大于$mid$的路径，我们所修改的边必定是这些路径所共同覆盖的，否则对于某条未覆盖此边的路径它的值不会改变，仍旧大于等于$mid$
在此基础上，修改所有路径共同覆盖的边中权值最大的一定最优。

那么一步步来。

首先是二分，这个肯定没有问题。
那么对于所有大于 mid 的路径，路径从大到小排序确定前缀大于$mid$的最靠后位置即可。路径长度可通过记录树上前缀和做到--不难想到，两个端点的树上前缀和之和减去两倍 $lca$ 的树上前缀和。
如何寻找被共同覆盖的边？
- 首先引入概念--树上前缀和与子树和。树上前缀和即是记录当前节点 $i$ 到根结点的距离，子树和则是以 $i$ 为根结点的子树内所有节点的权值和。
- 考虑利用子树和进行树上差分。我们将路径的左右端点的用于差分的数组 $+1$ ，然后如果此时我们统计整棵树所有结点的数组的子树和，我们会神奇地发现，从左端点以及右端点到 $lca$ 的路径上所有结点的子树和都为 $1$ ，从 $lca$ 到根结点的路径上所有结点的子树和都为 $2$ ！那么不难发现，如果我们在 $lca$ 的上再 $-1$ ，在 $lca$ 的父结点上也 $-1$，再计算一次子树和，就会发现此时这条路径上所有结点的数组子树和都为 $1$ ！也就是说，正好整条路径上的结点都 $+1$ 了！
- 只需要稍加修改，一个结点的子树和表示的是它到父结点的边的子树和，接着对于 $lca$ 我们改为在 $lca$ 处 $-2$ 并不对父结点处理即可！
- 所以差分真是个妙东西(小声bb)。
当对于所有的路径做完差分之后再统一做子树和后，对于每个子树和为大于 $mid$ 路径总数的点，它到父结点的边一定被这些路径同时经过，对于这些路径，我们取 $max$ 即可。
至于最长的路径，直接拿最长的路径减去 $max$ 并判断是否小于等于 $mid$ 即可。

然后这道题就轻松 A 掉了！

Code

// luogu-judger-enable-o2

// 开O2是因为有个点极度卡人，目前我已知的人里只有用树剖求LCA的过掉了......

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

int n, m, ans； int head[300001],

    f[300001][20];  // head数组用于链式前向星,f数组为倍增数组

int change[300001], jl[300001],

    num[300001];  // change数组为差分数组，jl(就是距离的首字母^_^)数组为树上前缀和，num数组为子树和

struct tree {

  int fa, deep;

} k[300001];  //记录树上结点信息

struct node {

  int u, v, lenth, lca;

} s[300001];  //路径信息

struct egde {

  int next, to, w;

} g[600001];  //边信息

int cmp(node x, node y) { return x.lenth > y.lenth; }

void read(int &x) {

  x = 0;

  char number = getchar();

  while (!isdigit(number)) number = getchar();

  while (isdigit(number)) {

    x = x * 10 + number - '0';

    number = getchar();

  }

}  //快读

void build(int x) {

  book[x] = 1;

  for (int p = head[x]; p; p = g[p].next)

    if (g[p].to != k[x].fa) {

      k[g[p].to].deep = k[x].deep + 1;

      k[g[p].to].fa = x;

      jl[g[p].to] = jl[x] + g[p].w;

      build(g[p].to);

    }

}  //建树，造出深度，父亲结点，树上前缀和的信息

int dfs(int x) {

  book[x] = 1;

  num[x] += change[x];

  int p = head[x];

  while (p) {

    if (g[p].to != k[x].fa) num[x] += dfs(g[p].to);

    p = g[p].next;

  }

  return num[x];

}  //统计子树和

bool pd(int mid) {

  int top = 1;

  for (int i = 1; i <= n; i++) {

    num[i] = 0;

    change[i] = 0;

    book[i] = 0;

  }

  while (s[top].lenth > mid && top <= m) top++;  //加入需要处理的路径

  top--;

  for (int i = 1; i <= top; i++) {

    change[s[i].u]++;

    change[s[i].v]++;

    change[s[i].lca] -= 2;

  }  //差分数组加减

  dfs(1);

  int maxx = 0;

  for (int i = 1; i <= n; i++)

    if (num[i] == top) maxx = max(maxx, jl[i] - jl[k[i].fa]);  //取最大值

  if (s[1].lenth - maxx <= mid) return true;

  return false;

}  //判断mid是否可行

int LCA(int a, int b) {

  if (k[a].deep > k[b].deep) {

    for (int j = 19; j >= 0; j--)

      if (k[f[a][j]].deep >= k[b].deep) a = f[a][j];

  } else

    for (int j = 19; j >= 0; j--)

      if (k[f[b][j]].deep >= k[a].deep) b = f[b][j];

  for (int j = 19; j >= 0; j--)

    if (f[a][j] != f[b][j]) {

      a = f[a][j];

      b = f[b][j];

    }

  if (a == b) return a;

  return k[a].fa;

}  //倍增求lca

int main() {

  read(n);

  read(m);

  int u, v, w;

  for (int i = 1; i < n; i++) {

    read(u);

    read(v);

    read(w);

    g[i].to = v;

    g[i].next = head[u];

    head[u] = i;

    g[i + n].to = u;

    g[i + n].next = head[v];

    head[v] = i + n;

    g[i].w = g[i + n].w = w;

  }  //存边

  k[1].deep = 1;

  build(1);

  for (int i = 1; i <= n; i++) f[i][0] = k[i].fa;

  for (int j = 1; j <= 19; j++)

    for (int i = 1; i <= n; i++)

      f[i][j] = f[f[i][j - 1]][j - 1];  //倍增数组处理

  for (int i = 1; i <= m; i++) {

    read(s[i].u);

    read(s[i].v);

    s[i].lca = LCA(s[i].u, s[i].v);

    s[i].lenth = jl[s[i].u] + jl[s[i].v] - jl[s[i].lca] * 2;

  }  //处理路径相关信息

  sort(s + 1, s + m + 1, cmp);

  int l = 1, r = s[1].lenth;

  ans = r;

  while (l <= r) {

    int mid = (l + r) / 2;

    if (pd(mid)) {

      ans = min(ans, mid);

      r = mid - 1;

    } else

      l = mid + 1;

  }  //二分答案

  cout << ans;

}

码农公寓