fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int oo = 2e9;
  7. const int N = 1e5+5;
  8. const int LG = 18;
  9.  
  10. int n, q;
  11. vector<pair<int, int>> adj[N];
  12. bool removed[N];
  13. int bit[N];
  14. int tin[N], tout[N], timer = 0;
  15. int depth[N], up[N][LG], min_w[N][LG];
  16.  
  17. void update(int p, int v) {
  18.     for (; p <= n; p += p & -p) bit[p] += v;
  19. }
  20.  
  21. int query(int p) {
  22.     int s = 0;
  23.     for (; p > 0; p -= p & -p) s += bit[p];
  24.     return s;
  25. }
  26.  
  27. int get(int u) {
  28.     return query(tin[u]);
  29. }
  30.  
  31. void dfs(int u, int p, int w) {
  32.     tin[u] = ++timer;
  33.     up[u][0] = p;
  34.     min_w[u][0] = w;
  35.     for (int i = 1; i < LG; i++) {
  36.         up[u][i] = up[up[u][i - 1]][i - 1];
  37.         min_w[u][i] = min(min_w[u][i - 1], min_w[up[u][i - 1]][i - 1]);
  38.     }
  39.     for (auto [v, c] : adj[u]) {
  40.         if (v == p) continue;
  41.         depth[v] = depth[u] + 1;
  42.         dfs(v, u, c);
  43.     }
  44.     tout[u] = timer;
  45. }
  46.  
  47. pair<int, int> get_lca(int u, int v) {
  48.     if (depth[u] < depth[v]) swap(u, v);
  49.     int ans = oo;
  50.     for (int i = LG - 1; i >= 0; i--)
  51.         if (depth[u] - (1 << i) >= depth[v]) {
  52.             ans = min(ans, min_w[u][i]);
  53.             u = up[u][i];
  54.         }
  55.     if (u == v) return {u, ans};
  56.     for (int i = LG - 1; i >= 0; i--)
  57.         if (up[u][i] != up[v][i]) {
  58.             ans = min({ans, min_w[u][i], min_w[v][i]});
  59.             u = up[u][i];
  60.             v = up[v][i];
  61.         }
  62.     ans = min({ans, min_w[u][0], min_w[v][0]});
  63.     return {up[u][0], ans};
  64. }
  65.  
  66. void solve() {
  67.     cin >> n >> q;
  68.     for (int i = 0; i < n - 1; i++) {
  69.         int u, v, w; cin >> u >> v >> w;
  70.         adj[u].emplace_back(v, w);
  71.         adj[v].emplace_back(u, w);
  72.     }
  73.     for (int i = 0; i < LG; i++) min_w[0][i] = oo;
  74.     dfs(1, 0, oo);
  75.     while (q--) {
  76.         int type; cin >> type;
  77.         if (type == 1) {
  78.             int u, v; cin >> u >> v;
  79.             if (u == v) {
  80.                 cout << "0\n";
  81.                 continue;
  82.             }
  83.             auto [lca, ans] = get_lca(u, v);
  84.             int cnt = get(u) + get(v) - 2 * get(lca) + removed[lca];
  85.             cout << (cnt > 0 ? -1 : ans) << '\n';
  86.         } else if (type == 2) {
  87.             int u; cin >> u;
  88.             if (!removed[u]) {
  89.                 removed[u] = 1;
  90.                 update(tin[u], 1);
  91.                 update(tout[u] + 1, -1);
  92.             }
  93.         }
  94.     }
  95. }
  96.  
  97. int main() {
  98.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  99.  
  100.     #define TASK "BACKUP"
  101.     if (fopen(TASK".INP", "r")) {
  102.         freopen(TASK".INP", "r", stdin);
  103.         freopen(TASK".OUT", "w", stdout);
  104.     }
  105.  
  106.     int tests = 1; // cin >> tests;
  107.     while (tests--) solve();
  108.  
  109.     #ifdef LOCAL
  110.     cerr << "\nTime elapsed: " << clock() << " ms.\n";
  111.     #endif
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0.01s 10040KB
comments (?)
stdin
copy 
4 4
1 2 3
2 3 4
2 4 2
1 3 4
2 2
1 3 4
1 1 1
stdout
copy 
2
-1
0
https://ideone.com/hDQJCT
Chọn Đội tuyển HSGQG Bắc Ninh 2025 - Kế hoạch dự phòng - Euler Tour
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!