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. struct Query {
  11.     int type, u, v;
  12. } qs[N];
  13.  
  14. int n, q;
  15. vector<pair<int, int>> adj[N];
  16. int destroyed[N], ans[N];
  17.  
  18. bool active[N];
  19. int P[N];
  20. int depth[N], up[N][LG], min_w[N][LG];
  21.  
  22. int find(int u) {
  23.     return P[u] == u ? u : P[u] = find(P[u]);
  24. }
  25.  
  26. void join(int u, int v) {
  27.     u = find(u); v = find(v);
  28.     if (u != v) P[v] = u;
  29. }
  30.  
  31. void dfs(int u, int p, int w) {
  32.     up[u][0] = p;
  33.     min_w[u][0] = w;
  34.     for (int i = 1; i < LG; i++) {
  35.         up[u][i] = up[up[u][i - 1]][i - 1];
  36.         min_w[u][i] = min(min_w[u][i - 1], min_w[up[u][i - 1]][i - 1]);
  37.     }
  38.     for (auto [v, c] : adj[u]) {
  39.         if (v == p) continue;
  40.         depth[v] = depth[u] + 1;
  41.         dfs(v, u, c);
  42.     }
  43. }
  44.  
  45. int get_ans(int u, int v) {
  46.     if (depth[u] < depth[v]) swap(u, v);
  47.     int ans = oo;
  48.     for (int i = LG - 1; i >= 0; i--)
  49.         if (depth[u] - (1 << i) >= depth[v]) {
  50.             ans = min(ans, min_w[u][i]);
  51.             u = up[u][i];
  52.         }
  53.     if (u == v) return ans;
  54.     for (int i = LG - 1; i >= 0; i--)
  55.         if (up[u][i] != up[v][i]) {
  56.             ans = min({ans, min_w[u][i], min_w[v][i]});
  57.             u = up[u][i];
  58.             v = up[v][i];
  59.         }
  60.     return min({ans, min_w[u][0], min_w[v][0]});;
  61. }
  62.  
  63. void solve() {
  64.     cin >> n >> q;
  65.     for (int i = 0; i < n - 1; i++) {
  66.         int u, v, w; cin >> u >> v >> w;
  67.         adj[u].emplace_back(v, w);
  68.         adj[v].emplace_back(u, w);
  69.     }
  70.     for (int i = 0; i < LG; i++) min_w[0][i] = oo;
  71.     dfs(1, 0, oo);
  72.     for (int i = 1; i <= q; i++) {
  73.         cin >> qs[i].type;
  74.         if (qs[i].type == 1) cin >> qs[i].u >> qs[i].v;
  75.         else {
  76.             cin >> qs[i].u;
  77.             destroyed[qs[i].u]++;
  78.         }
  79.     }
  80.     for (int i = 1; i <= n; i++) {
  81.         P[i] = i;
  82.         if (!destroyed[i]) active[i] = 1;
  83.     }
  84.     for (int u = 1; u <= n; u++) {
  85.         if (!active[u]) continue;
  86.         for (auto [v, c] : adj[u])
  87.             if (active[v]) join(u, v);
  88.     }
  89.     for (int i = q; i >= 1; i--) {
  90.         if (qs[i].type == 1) {
  91.             int u = qs[i].u, v = qs[i].v;
  92.             if (u == v) ans[i] = 0;
  93.             else if (find(u) == find(v)) ans[i] = get_ans(u, v);
  94.             else ans[i] = -1;
  95.         } else {
  96.             int u = qs[i].u;
  97.             destroyed[u]--;
  98.             if (!destroyed[u]) {
  99.                 active[u] = 1;
  100.                 for (auto [v, c] : adj[u])
  101.                     if (active[v]) join(u, v);
  102.             }
  103.         }
  104.     }
  105.     for (int i = 1; i <= q; i++)
  106.         if (qs[i].type == 1) cout << ans[i] << '\n';
  107. }
  108.  
  109. int main() {
  110.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  111.  
  112.     #define TASK "BACKUP"
  113.     if (fopen(TASK".INP", "r")) {
  114.         freopen(TASK".INP", "r", stdin);
  115.         freopen(TASK".OUT", "w", stdout);
  116.     }
  117.  
  118.     int tests = 1; // cin >> tests;
  119.     while (tests--) solve();
  120.  
  121.     #ifdef LOCAL
  122.     cerr << "\nTime elapsed: " << clock() << " ms.\n";
  123.     #endif
  124.     return 0;
  125. };
  126.  
Success #stdin #stdout 0s 9724KB
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/UpmAWv
Chọn Đội tuyển HSGQG Bắc Ninh 2025 - Kế hoạch dự phòng - DSU
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!