fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define el "\n"
  5. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define __ROOT__ int main()
  7. #define fi first
  8. #define se second
  9. #define M 1000000007
  10. #define MAXN 100001
  11. #define GIOIHAN 1000001
  12. #define BLOCK_SIZE 425
  13. #define MAX_NODE 1001001
  14. #define LOG 19
  15. #define ALPHA_SIZE 26
  16. #define BASE 311
  17. #define NAME "check"
  18. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); // dùng để nén sort mảng compare
  19. using namespace std;
  20. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  21. const ll NMOD = 1;
  22. const int dx[] = {-1, 0, 1,0};
  23. const int dy[] = {0, 1, 0, -1};
  24. //**Variable**//
  25. ll n ;
  26. ll tour[MAXN] ;
  27. ll par[MAXN] ;
  28. ll fin[MAXN] ;
  29. ll st[MAXN] ;
  30. ll high[MAXN] ;
  31. ll sz[MAXN] ;
  32. ll chainHead[MAXN] ;
  33. ll chainID[MAXN] ;
  34. ll NodeVal[MAXN] ;
  35. ll curchain = 1  ;
  36. ll timedfs =0 ;
  37. vector<ll>adj[MAXN] ;
  38. //**Struct**//
  39. struct E {
  40.     ll u, v, w;
  41.  
  42. };
  43. vector<E> edge ;
  44. struct Seg {
  45.     struct Data {
  46.         ll mi, ma  ;
  47.     };
  48.     Data val[MAXN << 2 ] ;
  49.     ll lazy[MAXN<<2 ] ;
  50.     void resett() {
  51.         for(ll i = 0  ; i <(MAXN <<2  ) ; i ++ ) {
  52.             val[i].ma = INT_MIN;val[i]. mi = INT_MAX ;
  53.         }
  54.         memset(lazy, 0, sizeof lazy  ) ;
  55.     }
  56.     Data Merge(Data a, Data b ) {
  57.         Data res  ;
  58.         res.ma = max(a.ma, b.ma ) ;
  59.         res.mi = min(a.mi, b.mi)  ;
  60.         return res ;
  61.     }
  62.     void build(ll id, ll l,ll r ) {
  63.         if(l == r ) {
  64.             val[id].mi = val[id].ma = NodeVal[tour[l]];
  65.         } else {
  66.             ll m = (l + r) >> 1 ;
  67.             build(id<<1, l, m ) ;
  68.             build(id<<1|1, m + 1, r  ) ;
  69.             val[id ] =Merge(val[id<<1], val[id<<1|1]) ;
  70.         }
  71.     }
  72.     void fix(ll id,  ll l, ll r ) {
  73.         if(lazy[id]) {
  74. //            ll tmp_ma = val[id].ma ;
  75. //            ll tmp_mi = val[id].mi ;
  76.             swap(val[id].ma, val[id].mi);
  77.             val[id].ma = -val[id].ma ;
  78.             val[id].mi = -val[id].mi;
  79.             if(l!=r ) {
  80.                 lazy[id<<1] ^= lazy[id] ;
  81.                 lazy[id<<1|1] ^=lazy[id] ;
  82.             }
  83.             lazy[id]  = 0 ;
  84.         }
  85.     }
  86.     void update(ll id, ll l, ll r, ll u, ll v ) {
  87.         fix(id, l, r) ;
  88.         if(u > r  || v < l   ) return  ;
  89.         if(u <= l && v >= r ) {
  90.             lazy[id] ^= 1 ;
  91.             fix(id, l, r ) ;
  92.             return ;
  93.         }
  94.         ll m = (l + r) >> 1 ;
  95.         update(id<< 1, l, m, u,  v );
  96.         update(id<<1|1, m + 1, r, u, v  ) ;
  97.         val[id] = Merge(val[id<<1], val[id<<1|1]) ;
  98.     }
  99.  
  100.     ll get(ll id, ll l, ll r,ll u, ll v ) {
  101.         fix(id, l, r  )  ;
  102.         if(u > r || v < l ) return INT_MIN  ;
  103.         if(u <= l && v >= r ) {
  104.             return val[id].ma ;
  105.         }
  106.         ll m = (l + r) >> 1 ;
  107.         return max(get(id<<1,  l, m, u, v ), get(id<< 1 |1, m + 1, r, u, v ))  ;
  108.     }
  109.  
  110.     void updatepos(ll id , ll l ,ll r , ll u , ll v  , ll value) {
  111.     fix(id , l , r  ) ;
  112.     if(u > r || v < l ) return ;
  113.     if(u <= l && v >= r  ) {
  114.         val[id].ma = val[id].mi = value  ;
  115.         return ;
  116.     }
  117.     ll m = l  + r >> 1;
  118.     updatepos(id<<1 , l , m  , u , v ,value) ;
  119.     updatepos(id<<1|1 , m + 1 , r ,u , v , value ) ;
  120.     val[id] =Merge(val[id<<1] , val[id<<1|1]) ;
  121.     }
  122. } seg;
  123. //**Function**//
  124. void resetall() {
  125.     memset(tour, 0, sizeof tour) ;
  126.     memset(par, 0, sizeof par) ;
  127.     memset(st, 0, sizeof st) ;
  128.     memset(fin, 0, sizeof fin) ;
  129.     memset(high, 0, sizeof high) ;
  130.     memset(sz, 0, sizeof sz) ;
  131.     memset(chainHead, 0, sizeof chainHead) ;
  132.     memset(chainID, 0, sizeof chainID) ;
  133.     memset(NodeVal, 0, sizeof NodeVal ) ;
  134.     seg.resett();
  135.     edge.resize(0) ;
  136.     curchain = 1  ;
  137.     timedfs =0 ;
  138.     for(ll i = 0 ; i <= n ; i ++ ) adj[i].resize(0);
  139. }
  140. void dfs(ll u, ll p ) {
  141.     sz[u] = 1 ;
  142.     for(ll v : adj[u]) {
  143.         if(p != v ) {
  144.             high[v] = high[u] + 1 ;
  145.             par[v]= u ;
  146.             dfs(v, u) ;
  147.             sz[u] += sz[v];
  148.         }
  149.     }
  150. }
  151.  
  152. void hld(ll u, ll p ) {
  153.     if(!chainHead[curchain]) {
  154.         chainHead[curchain ] = u ;
  155.     }
  156.     st[u] = ++ timedfs ;
  157.     tour[timedfs] = u;
  158.     chainID[u]= curchain ;
  159.     ll nxt = 0 ;
  160.     for(ll v : adj[u]) {
  161.         if(v == p ) continue ;
  162.         if(nxt == 0 || sz[v] > sz[nxt]) nxt = v;
  163.     }
  164.     if(nxt) hld(nxt, u) ;
  165.     for(ll v : adj[u]) {
  166.         if(v != p && v != nxt ) {
  167.             curchain ++ ;
  168.             hld(v, u ) ;
  169.         }
  170.     }
  171.     fin[u] = timedfs ;
  172. }
  173. ll LCA(ll u, ll v) {
  174.     while (chainID[u] != chainID[v]) {
  175.  
  176.         if (high[chainHead[chainID[u]]] > high[chainHead[chainID[v]]])
  177.             u = par[chainHead[chainID[u]]];
  178.         else
  179.             v = par[chainHead[chainID[v]]];
  180.     }
  181.     return high[u] < high[v] ? u : v;
  182. }
  183.  
  184. ll query(ll u, ll v ) {
  185.       if (u == v) {
  186.                return 0 ;
  187.             }
  188.     ll lca = LCA(u, v), ma = INT_MIN ;
  189.     while(chainID[u] != chainID[lca]) {
  190.         ma = max(ma, seg.get(1, 1, n,st[chainHead[chainID[u]]]   , st[u] ));
  191.         u = par[chainHead[chainID[u]]];
  192.     }
  193.     while(chainID[v] != chainID[lca]) {
  194.         ma = max(ma, seg.get(1, 1, n, st[chainHead[chainID[v]]]  , st[v] ));
  195.         v = par[chainHead[chainID[v]]] ;
  196.     }
  197.     if(u == v ) return ma ;
  198.     if(high[u] > high[v]) swap(u, v ) ;
  199.     return max(ma, seg.get(1, 1, n, st[u] + 1, st[v])) ;
  200. }
  201. void daodau(ll u, ll v ) {
  202.     ll lca = LCA(u, v) ;
  203.     while(chainID[u] != chainID[lca]) {
  204.         seg.update(1, 1, n, st[chainHead[chainID[u]]]    , st[u] );
  205.         u = par[chainHead[chainID[u]]] ;
  206.     }
  207.     while(chainID[v] != chainID[lca]) {
  208.         seg.update(1, 1, n,st[chainHead[chainID[v]]] , st[v] );
  209.         v = par[chainHead[chainID[v]]] ;
  210.     }
  211.     if(u == v ) return ;
  212.     if(high[u] > high[v]) swap(u, v ) ;
  213.     seg.update(1, 1, n, st[u] + 1, st[v]) ;
  214. }
  215. void init() {
  216.     cin>>n ;
  217.     for(ll i = 1 ; i <= n - 1 ; i ++ ) {
  218.         ll x, y, w ;
  219.         cin>>x>>y>>w ;
  220.         edge.push_back({x, y, w }) ;
  221.         adj[x].push_back(y ) ;
  222.         adj[y].push_back(x)  ;
  223.     }
  224.     dfs(1, 1   ) ;
  225.     for(ll i = 0 ; i < edge.size() ; i ++ )  {
  226.         ll u = edge[i].u;
  227.         ll v = edge[i].v ;
  228.         if(u == par[v]) swap(u, v ) ;// u : child
  229.         NodeVal[u] = edge[i].w;
  230.     }
  231.     hld(1, 1 ) ;
  232.     seg.build(1, 1, n );
  233. }
  234.  
  235. void solve() {
  236. //    cout<<LCA(2 , 5) << " dưa" ;
  237. //cout<<st[9] << " ew" << el ;
  238.     string str;
  239.     do {
  240.         cin>>str;
  241. //          cout<<str<<el ;
  242.         if (str == "DONE") return ;
  243. //            cout<<str<<el ;
  244.         if (str == "QUERY") {
  245.             ll x, y ;
  246.             cin >> x >> y;
  247.             cout << query(x, y) << el;
  248.         } else if (str == "NEGATE") {
  249.             ll x, y ;
  250.             cin >> x >> y;
  251.             daodau(x, y);
  252.         } else if(str == "CHANGE" ) {
  253.             ll x, y ;
  254.             cin >> x >> y;
  255.             ll u = edge[x - 1].u;
  256.             ll v = edge[x - 1].v;
  257.             edge[x-1 ].w = y ;
  258.             if (u == par[v]) swap(u, v); // u : child
  259.             seg.updatepos(1, 1, n, st[u] , st[u], y);
  260.         }
  261.     } while(str != "DONE") ;
  262. }
  263.  
  264.  
  265. __ROOT__ {
  266. //    freopen(NAME".inp" , "r" , stdin);
  267. //              freopen(NAME".out" , "w", stdout) ;
  268.     fast;
  269.     ll t;
  270.     cin >> t;
  271.     for(ll i = 1 ; i <= t ; i ++ ) {
  272.         init();
  273.         solve();
  274.         resetall() ;
  275.     }
  276. }
  277.  
  278.  
Success #stdin #stdout 0.01s 22360KB
comments (?)
stdin
copy 
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout
copy 
1
3
https://ideone.com/dElouR
language:
C++14 (gcc 8.3)
created:
244 days 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!