NC13331 城市网络

题目地址：

https://ac.nowcoder.com/acm/problem/13331

基本思路：

由于数据更新我们的旧解法已经完美的TLE了;
所以新的思路肯定不能暴力了,我们还是抓住保证 v 在 u 前往首都的最短路径上这句话,使用倍增优化;
不理解倍增的同学可以上网搜一搜倍增,学习一下,其实就是有点类似于并查集中find操作进化,递推式为 f[s][i] = f[f[s][i - 1]][i - 1], i 代表向上走 2^i 步;
那么我们的倍增数组记录的是什么呢,我们的倍增数组记录,祖先节点中比第一个当前的节点值大的节点,为倍增数组中该节点的上一个节点;
那么我们通过倍增的寻找 u -> v 路线在倍增数组里要向上走的步数即是答案;
为了方便计算,我们将查询也作为一个节点,位置在查询时的u节点下方,大小为给出的初始宝石价格,具体细节可以看代码注释。

参考代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 2e5 + 10;
int n,q,w[maxn],f[maxn][20],dep[maxn],to[maxn];
vector<int> G[maxn];
void dfs(int s,int parent) {
  dep[s] = dep[parent] + 1;//更新深度;
  int x = parent;
  for (int i = 19; i >= 0; i--) {
    if (w[f[x][i]] <= w[s] && f[x][i]) x = f[x][i];
    //往上倍增寻找第一个比w[s]大的节点下面那个节点(他的父亲就是第一个比w[s]大的节点);
  }
  if (w[x] > w[s]) f[s][0] = x;//没找到那这个就是最大的那个;
  else f[s][0] = f[x][0];
  for (int i = 1; i < 20; i++) {
    f[s][i] = f[f[s][i - 1]][i - 1];//更新倍增数组;
  }
  for (auto v : G[s]) {
    if (v == parent) continue;
    dfs(v, s);
  }
}
signed main() {
  n = read(),q = read();
  rep(i, 1, n) w[i] = read();
  rep(i, 1, n - 1) {
    int u, v;
    u = read(),v = read();
    G[u].push_back(v);
    G[v].push_back(u);
  }
  rep(i, n + 1, n + q) {//这里我们将查询作为一个节点,连在u节点下方,方便寻找答案;
    int x, y, z;
    x = read(),y = read(),z = read();
    G[i].push_back(x);
    G[x].push_back(i);
    w[i] = z;
    to[i - n] = y;//这个查询时的u节点对应的v节点;
  }
  dfs(1, 0);
  rep(i, 1, q) {
    int ans = 0;
    int x = i + n;//这次查询时u节点在图中代表的节点;
    for (int j = 19; j >= 0; j--) {
      if (dep[f[x][j]] >= dep[to[i]]) {//从u往上倍增找,位置不能超过v的位置;
        ans += (1 << j);//往上走了几步,即宝石更新了几次;
        x = f[x][j];
      }
    }
    cout << ans << endl;
  }
  return 0;
}