fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(v) v.begin(),v.end()
  4. #define MASK(i) (1LL << (i))
  5. #define ii pair<int,int>
  6. #define fi first
  7. #define se second
  8. #define endl '\n'
  9. #define forr(i,l,r,add) for(int i = l;i <= r; i = i + add)
  10. #define fodd(i,l,r,sub) for(int i = l;i >= r ; i = i - sub)
  11. template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
  12. template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
  13.  
  14. using namespace std;
  15.  
  16. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  17. #define rand rd
  18.  
  19. long long Rand(long long l , long long h){
  20. 	assert(l <= h);
  21. 	return l + 1ll * rd() % (h - l + 1) * (rd() % (h - l + 1)) % (h - l + 1);
  22. }
  23.  
  24.  
  25. //////////////////////////////////////////////////////////// end of template ////////////////////////////////////////////////////////////
  26.  
  27. const int MAX = 15e4 + 5;
  28. int n , m , q;
  29. vector <int> edge[MAX];
  30. int child[MAX];
  31. int par[MAX];
  32. int lazy[(1 << 19) + 5] , segment[(1 << 19) + 5];
  33. int ID[MAX] , ST[MAX] , in[MAX];
  34. int dinh[MAX];
  35. int cnt_ID , cnt_HLD;
  36.  
  37. void dfs(int u){
  38.     child[u] = 1;
  39.     for(auto x : edge[u]){
  40.         if(x != par[u]){
  41.             par[x] = u;
  42.             dfs(x);
  43.             child[u] += child[x];
  44.         }
  45.     }
  46. }
  47.  
  48. void build(int u , bool ok){
  49.     ID[u] = ++cnt_ID;
  50.     dinh[cnt_ID] = u;
  51.     if(ok){
  52.         in[ID[u]] = cnt_HLD;
  53.     }
  54.     else {
  55.         in[ID[u]] = ++cnt_HLD;
  56.         ST[cnt_HLD] = ID[u];
  57.     }
  58.     int mx = 0 , d = 0;
  59.     for(auto x : edge[u]) if(x != par[u] && child[x] > mx) mx = child[x] , d = x;
  60.     if(d != 0) build(d , 1);
  61.     for(auto x : edge[u]) if(x != par[u] && x != d) build(x , 0);
  62. }
  63.  
  64. void push_down(int id , int i , int j){
  65.     maximize(segment[id] , lazy[id]);
  66.     if(i != j){
  67.         maximize(lazy[id << 1] , lazy[id]);
  68.         maximize(lazy[id << 1 | 1] , lazy[id]);
  69.     }
  70.     lazy[id] = -1;
  71. }
  72. void up(int id , int i , int j , int l , int r , int val){
  73.     push_down(id , i , j);
  74.     if(j < l || i > r || i > j) return;
  75.     if(l <= i && j <= r){
  76.         lazy[id] = val;
  77.         push_down(id , i , j);
  78.         return;
  79.     }
  80.     int m = i + j >> 1;
  81.     up(id << 1 , i , m , l , r , val);
  82.     up(id << 1 | 1 , m + 1 , j , l , r , val);
  83.     segment[id] = min(segment[id << 1] , segment[id << 1 | 1]);
  84. }
  85.  
  86. void update(int x , int y , int val){
  87.     while(in[ID[x]] != in[ID[y]]){
  88.         if(in[ID[x]] > in[ID[y]]) swap(x , y);
  89.         up(1 , 2 , n , ST[in[ID[y]]] , ID[y] , val);
  90.         y = par[dinh[ST[in[ID[y]]]]];
  91.     }
  92.     up(1 , 2 , n , min(ID[x] , ID[y]) + 1 , max(ID[x] , ID[y]) , val);
  93. }
  94.  
  95. void INP(){
  96.     cin >> n;
  97.     forr(i , 1 , n - 1 , 1){
  98.         int x , y;
  99.         cin >> x >> y;
  100.         edge[x].push_back(y);
  101.         edge[y].push_back(x);
  102.     }
  103.     dfs(1);
  104.     build(1 , 0);
  105.     memset(lazy , -1 , sizeof(lazy));
  106.     memset(segment , -1 , sizeof(segment));
  107.     cin >> m;
  108.     while(m--){
  109.         int x , y , val;
  110.         cin >> x >> y >> val;
  111.         update(x , y , val);
  112.     }
  113.     cout << segment[1] << endl;
  114.     cin >> q;
  115.     while(q--){
  116.         int x , y , val;
  117.         cin >> x >> y >> val;
  118.         update(x , y , val);
  119.         cout << segment[1] << endl;
  120.     }
  121. }
  122.  
  123. int main()
  124. {
  125.     ios_base::sync_with_stdio(false);
  126.     cin.tie(0);
  127.     cout.tie(0);
  128.     #define TASK ""
  129.     //freopen(TASK".inp" , "r" , stdin);
  130.     //freopen(TASK".out" , "w" , stdout);
  131.     INP();
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0.01s 13716KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/XxVpS2
language:
C++14 (gcc 8.3)
created:
3 days 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!