11-22模拟赛

Dash Speed

题目描述

比特山是比特镇的飙车圣地。在比特山上一共有 $n$ 个广场，编号依次为 $1$ 到 $n$，这些广场之间通过 $n-1$ 条双向车道直接或间接地连接在一起，形成了一棵树的结构。

因为每条车道的修建时间以及建筑材料都不尽相同，所以可以用两个数字 $l_i,r_i$ 量化地表示一条车道的承受区间，只有当汽车以不小于 $l_i$ 且不大于 $r_i$ 的速度经过这条车道时，才不会对路面造成伤害。

Byteasar 最近新买了一辆跑车，他想在比特山飙一次车。Byteasar 计划选择两个不同的点 $S，T$ 然后在它们树上的最短路径上行驶，且不对上面任意一条车道造成伤害。

Byteasar 不喜欢改变速度，所以他会告诉你他的车速。为了挑选出最合适的车速，Byteasar 一共会向你询问 $m$ 次。请帮助他找到一条合法的道路，使得路径上经过的车道数尽可能多。

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>

template <typename T>
inline T& read(T& x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 7e4 + 5;
int n, m, heads[N], e_cnt, dep[N], siz[N], fa[N], son[N], top[N], ans[N];

struct Edge {
  int nxt, v;
  Edge() {}
  Edge(int u, int v) : nxt(u), v(v) {}
} e[N << 1];

void add(int u, int v) {
  e[++e_cnt].v = v, e[e_cnt].nxt = heads[u], heads[u] = e_cnt;
}

void dfs1(int u, int f) {
  fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
  for (int j = heads[u], v; j; j = e[j].nxt)
    if ((v = e[j].v) != f) {
      dfs1(v, u), siz[u] += siz[v];
      if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

void dfs2(int u, int Top) {
  top[u] = Top;
  if (son[u]) dfs2(son[u], Top);
  for (int j = heads[u], v; j; j = e[j].nxt)
    if ((v = e[j].v) != fa[u] && v != son[u]) dfs2(v, v);
}

inline int getlca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
    x = fa[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}

inline int getdis(int x, int y) {
  return dep[x] + dep[y] - (dep[getlca(x, y)] << 1);
}

struct Node {
  int a, b, w;
  Node() {}
  Node(int a, int b, int w) : a(a), b(b), w(w) {}

  inline void operator()(const Node& rhs) {
    int tmp = getdis(a, rhs.a), orib = this->b;
    if (w < tmp) this->b = rhs.a, this->w = tmp;
    tmp = getdis(a, rhs.b);
    if (w < tmp) this->b = rhs.b, this->w = tmp;
    tmp = getdis(orib, rhs.a);
    if (w < tmp) this->a = orib, this->b = rhs.a, this->w = tmp;
    tmp = getdis(orib, rhs.b);
    if (w < tmp) this->a = orib, this->b = rhs.b, this->w = tmp;
    if (w < rhs.w) *this = rhs;
  }
};

struct Segtree {
  struct UFSNode {
    Node s;
    int fa, dep;
  } p[N];

  struct Node {
    int u;
    UFSNode p0;
    Node(int u, const UFSNode& p0) : u(u), p0(p0) {}
  };

  std::vector<Edge> E[N << 2];
  std::stack<Node> stk;

  void insert(int x, int l, int r, int L, int R, const Edge& e) {
    if (L <= l && r <= R) return E[x].emplace_back(e);
    int mid = (l + r) >> 1;
    if (L <= mid) insert(x << 1, l, mid, L, R, e);
    if (mid < R) insert(x << 1 | 1, mid + 1, r, L, R, e);
  }

  int find(int u) { return u == p[u].fa ? u : find(p[u].fa); }

  inline void merge(int u, int v, int& len) {
    u = find(u), v = find(v);
    if (u == v) return;
    if (p[u].dep > p[v].dep) std::swap(u, v);
    stk.push(Node(u, p[u])), stk.push(Node(v, p[v]));
    p[v].s(p[u].s), p[u].fa = v;
    if (p[u].dep == p[v].dep) ++p[v].dep;
    len = std::max(len, p[v].s.w);
  }

  void solve(int x, int l, int r, int len) {
    size_t ori = stk.size();
    for (auto& i : E[x]) merge(i.nxt, i.v, len);
    if (l == r) ans[l] = len;
    else {
      int mid = (l + r) >> 1;
      solve(x << 1, l, mid, len);
      solve(x << 1 | 1, mid + 1, r, len);
    }
    while (stk.size() != ori) {
      p[stk.top().u] = stk.top().p0;
      stk.pop();
    }
  }
} seg;

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("External.in", "r", stdin);
  freopen("External.out", "w", stdout);
#endif
#endif

  read(n), read(m);
  for (int i = 1, u, v, l, r; i < n; ++i) {
    read(u), read(v), read(l), read(r);
    add(u, v), add(v, u);
    seg.insert(1, 1, n, l, r, Edge(u, v));
  }
  dfs1(1, 0), dfs2(1, 1);
  for (int i = 1; i <= n; ++i)
    seg.p[i].fa = i, seg.p[i].dep = 1, seg.p[i].s = Node(i, i, 0);
  seg.solve(1, 1, n, 0);
  for (int i = 1, x; i <= m; ++i) printf("%d\n", ans[read(x)]);
  return 0;
}