제출 #1188981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188981		mannshah1211	Tourism (JOI23_tourism)	C++20	0 / 100	22 ms	9796 KiB

tourism

/**
 *   author: tourist
 *   created: 20.04.2025 16:24:10
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const int B = 350;

struct Query {
  int l, r, id;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, q;
  cin >> n >> m >> q;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> tin(n), tout(n);
  vector<vector<int>> pv(n, vector<int>(18));
  vector<int> depth(n);
  int timer = 0;
  auto Dfs = [&](auto&& self, int v, int pr) -> void {
    tin[v] = timer++;
    pv[v][0] = pr;
    for (int u : g[v]) {
      if (u != pr) {
        depth[u] = depth[v] + 1;
        self(self, u, v);
      }
    }
    tout[v] = timer;
  };
  Dfs(Dfs, 0, -1);
  vector<int> c(m);
  for (int i = 0; i < m; i++) {
    cin >> c[i];
    --c[i];
  }
  for (int j = 1; j < 18; j++) {
    for (int i = 0; i < n; i++) {
      if (pv[i][j - 1] == -1) {
        pv[i][j] = -1;
      } else {
        pv[i][j] = pv[pv[i][j - 1]][j - 1];
      }
    }
  }
  auto Anc = [&](int u, int v) {
    return (tin[u] <= tin[v]) && (tout[v] <= tout[u]);
  };
  auto lca = [&](int u, int v) {
    if (Anc(u, v)) {
      return u;
    }
    for (int b = 17; b >= 0; b--) {
      if (pv[u][b] != -1 && !Anc(pv[u][b], v)) {
        u = pv[u][b];
      }
    }
    return pv[u][0];
  };
  auto dist = [&](int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  };
  vector<int> ans(q);
  vector<Query> queries(q);
  for (int i = 0; i < q; i++) {
    cin >> queries[i].l >> queries[i].r;
    --queries[i].l; --queries[i].r;
    queries[i].id = i; 
  }
  sort(queries.begin(), queries.end(), [&](const auto &a, const auto &b) {
    return make_pair(a.l / B, a.r) < make_pair(b.l / B, b.r);
  });
  set<pair<int, int>> st;
  int answ = 0;
  auto Add = [&](int i) {
    st.insert(make_pair(tin[c[i]], c[i]));
    auto it = st.find(make_pair(tin[c[i]], c[i]));
    if (st.size() == 1) {
      return;
    }
    if (it == st.begin()) {
      answ -= dist(next(it)->second, (--st.end())->second);
      answ += dist(it->second, next(it)->second) + dist(it->second, (--st.end())->second);
    } else if (it == --st.end()) {
      answ -= dist(prev(it)->second, st.begin()->second);
      answ += dist(it->second, prev(it)->second) + dist(it->second, st.begin()->second);
    } else {
      answ -= dist(prev(it)->second, next(it)->second);
      answ += dist(it->second, prev(it)->second) + dist(it->second, next(it)->second);
    }
  };
  auto Remove = [&](int i) {
    auto it = st.find(make_pair(tin[c[i]], c[i]));
    if (st.size() == 1) {
      st.erase(it);
      return;
    }
    if (it == st.begin()) {
      answ += dist(next(it)->second, (--st.end())->second);
      answ -= dist(it->second, next(it)->second) + dist(it->second, (--st.end())->second);
    } else if (it == --st.end()) {
      answ += dist(prev(it)->second, st.begin()->second);
      answ -= dist(it->second, prev(it)->second) + dist(it->second, st.begin()->second);
    } else {
      debug(st, make_pair(tin[c[i]], c[i]));
      answ += dist(prev(it)->second, next(it)->second);
      answ -= dist(it->second, prev(it)->second) + dist(it->second, next(it)->second);
    }
    st.erase(it);
  };
  int l = 0, r = -1;
  for (int i = 0; i < q; i++) {
    while (l > queries[i].l) {
      l--;
      Add(l);
    }
    while (r < queries[i].r) {
      r++;
      Add(r);
    }
    while (l < queries[i].l) {
      Remove(l);
      l++;
    }
    while (r > queries[i].r) {
      Remove(r);
      r--;
    }
    ans[queries[i].id] = answ / 2;
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] + 1 << '\n';
  }
  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41