fork download
copy 
  1. #define __USE_MINGW_ANSI_STDIO 0
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <queue>
  9. #include <map>
  10. #include <unordered_map>
  11. #include <set>
  12. #include <unordered_set>
  13. #include <stack>
  14. #include <deque>
  15. #include <string.h>
  16. #include <sstream>
  17. #include <math.h>
  18.  
  19. using namespace std;
  20.  
  21. #define PI atan2(0, -1)
  22. #define epsilon 0.000000001
  23. #define INF 5000000000000000000
  24. #define MOD 1000000007
  25.  
  26. template<int sz>
  27. class HeavyLight{
  28. public:
  29.     struct Node{
  30.         int mini, lazy;
  31.         Node(){ mini = 2e9; lazy = 0; }
  32.     };
  33.  
  34.     int N, M, parents [sz+10], depths [sz+10], subtreeSizes [sz+10];
  35.     int heavy [sz+10], root [sz+10], segPos [sz+10];
  36.     Node tree [4*sz+10];
  37.     pair<int, int> originals [sz+10];
  38.     vector<pair<int, int>> adjacency [sz+10];
  39.     HeavyLight(){ memset(heavy, -1, sizeof(heavy)); }
  40.     void dfs(int curr, int prevy, int d){
  41.         depths[curr] = d; parents[curr] = prevy; subtreeSizes[curr] = 1;
  42.         int maxSubtree = 0;
  43.         for(pair<int, int> edge : adjacency[curr]){
  44.             if(edge.first == prevy) continue;
  45.             dfs(edge.first, curr, d+1);
  46.             if(subtreeSizes[edge.first] > maxSubtree) heavy[curr] = edge.first, maxSubtree = subtreeSizes[edge.first];
  47.             subtreeSizes[curr] += subtreeSizes[edge.first];
  48.         }
  49.     }
  50.  
  51.     int left(int p){ return p<<1; }
  52.     int right(int p){ return (p<<1)+1; }
  53.  
  54.     void pushDown(int p, int L, int R){
  55.         if(tree[p].lazy == 0) return;
  56.         tree[p].mini = min(tree[p].mini, tree[p].lazy);
  57.         int li = left(p), ri = right(p);
  58.         if(L != R){
  59.             tree[li].lazy = tree[p].lazy;
  60.             tree[ri].lazy = tree[p].lazy;
  61.         }
  62.         tree[p].lazy = 0;
  63.     }
  64.  
  65.     long long evalMini(int p){ return min(tree[p].mini, tree[p].lazy); }
  66.  
  67.     void pullUp(int p, int L, int R){
  68.         int li = left(p), ri = right(p);
  69.         tree[p].mini = min(evalMini(li), evalMini(ri));
  70.     }
  71.  
  72.     void update(int p, int L, int R, int i, int j, int val){
  73.         if(L > R || i > R || j < L) return;
  74.         if(L >= i && R <= j){ tree[p].lazy = val; return; }
  75.         pushDown(p, L, R);
  76.         int li = left(p), ri = right(p);
  77.         update(li, L, (L+R)/2, i, j, val); update(ri, (L+R)/2+1, R, i, j, val);
  78.         pullUp(p, L, R);
  79.     }
  80.  
  81.     int minQuery(int p, int L, int R, int i, int j){
  82.         if(L > R || i > R || j < L) return 2e9;
  83.         if(L >= i && R <= j) return evalMini(p);
  84.         pushDown(p, L, R);
  85.         int li = left(p), ri = right(p);
  86.         int ret = min(minQuery(li, L, (L+R)/2, i, j), minQuery(ri, (L+R)/2+1, R, i, j));
  87.         pullUp(p, L, R);
  88.         return ret;
  89.     }
  90.  
  91.     void HLD(){
  92.         for(int i = 0, currentPos = 0; i < N; i++)
  93.             if(parents[i] == -1 || heavy[parents[i]] != i)
  94.                 for(int j = i; j != -1; j = heavy[j]){
  95.                     root[j] = i;
  96.                     segPos[j] = currentPos++;
  97.                 }
  98.     }
  99.  
  100.     template<class BinaryOperation>
  101.     void processPath(int u, int v, BinaryOperation op){
  102.         for( ; root[u] != root[v]; v = parents[root[v]]){
  103.             if(depths[root[u]] > depths[root[v]]) swap(u, v);
  104.             op(segPos[root[v]], segPos[v]);
  105.         }
  106.         if(depths[u] > depths[v]) swap(u, v);
  107.         op(segPos[u]+1, segPos[v]);
  108.     }
  109.  
  110.     void modifyPath(int u, int v, int value){
  111.         processPath(u, v, [this, &value](int l, int r) { update(1, 0, N-1, l, r, value); });
  112.     }
  113.  
  114.     int queryPath(int u, int v) {
  115.         int ret = 2e9;
  116.         processPath(u, v, [this, &ret](int l, int r) { ret = min(ret, minQuery(1, 0, N-1, l, r)); });
  117.         return ret;
  118.     }
  119.  
  120. };
  121.  
  122.  
  123. int main(){
  124.     //freopen("disrupt.in", "r", stdin); freopen("disrupt.out", "w", stdout);
  125.     ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(18);
  126.     HeavyLight<50000> hld;
  127.     cin >> hld.N >> hld.M;
  128.     for(int i = 0; i < hld.N-1; i++){
  129.         int a, b; cin >> a >> b; a--; b--;
  130.         hld.originals[i] = make_pair(a, b);
  131.         hld.adjacency[a].push_back(make_pair(b, 2e9)); hld.adjacency[b].push_back(make_pair(a, 2e9));
  132.     }
  133.     hld.dfs(0, -1, 0); hld.HLD();
  134.     vector<pair<int, pair<int, int>>> queries;
  135.     for(int i = 0; i < hld.M; i++){
  136.         int a, b, c; cin >> a >> b >> c; a--; b--;
  137.         queries.push_back(make_pair(c, make_pair(a, b)));
  138.     }
  139.     sort(queries.begin(), queries.end());
  140.     for(int i = hld.M-1; i > -1; i--){
  141.         int a = queries[i].second.first, b = queries[i].second.second, c = queries[i].first;
  142.         hld.modifyPath(a, b, c);
  143.     }
  144.     for(int i = 0; i < hld.N-1; i++){
  145.         int ret = hld.queryPath(hld.originals[i].first, hld.originals[i].second);
  146.         if(ret == 2e9) cout << "-1\n";
  147.         else cout << ret << '\n';
  148.     }
  149.     return 0;
  150. }
  151.  
Success #stdin #stdout 0s 6428KB
comments (?)
stdin
copy 
6 3
1 2
1 3
4 1
4 5
6 5
2 3 7
3 6 8
6 4 5
stdout
copy 
7
7
8
5
5
https://ideone.com/e38P58
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!