fork download
copy 
  1. // LAT Le Anh Tuan
  2. // CEAAURK
  3. #include <bits/stdc++.h>
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define ld long double
  7. #define se second
  8. #define fi first
  9. #define MOD 1000000007
  10. #define MAX 1000000000
  11. using namespace std;
  12.  
  13. ll n, q, H, timerHLD, t;
  14. ll dep[100005], par[100005];
  15. ll head[100005], heavy[100005], pos[100005], sz[100005];
  16. vector<ll> vec[100005];
  17. struct seg{ll mx, mn, lazy;};
  18. seg tree[200005];
  19. struct Edge{ll u, v, w;};
  20. vector<Edge> canh;
  21.  
  22. void build(ll u, ll p){
  23.     dep[u]=dep[p]+1;
  24.     par[u]=p;
  25.     sz[u]=1;
  26.  
  27.     ll mx=0;
  28.     for(auto v:vec[u]){
  29.         if(v==p)continue;
  30.         build(v, u);
  31.         sz[u]+=sz[v];
  32.         if(sz[v]>mx)mx=sz[v], heavy[u]=v;
  33.     }
  34. }
  35.  
  36. void buildHLD(ll u, ll h){
  37.     head[u]=h;
  38.     pos[u]=++timerHLD;
  39.     if(heavy[u])buildHLD(heavy[u], h);
  40.     for(auto v:vec[u]){
  41.         if(v==par[u] or v==heavy[u])continue;
  42.         buildHLD(v, v);
  43.     }
  44. }
  45.  
  46. void apply(ll u, ll val){
  47.     auto [mx, mn, lazy]=tree[u];
  48.     if(val%2==1)tree[u].mx=-mn, tree[u].mn=-mx;
  49.     tree[u].lazy+=val;
  50. }
  51.  
  52. void push(ll u){
  53.     if(u<=n){
  54.         apply(u*2, tree[u].lazy);
  55.         apply(u*2+1, tree[u].lazy);
  56.     }
  57.     tree[u].lazy=0;
  58. }
  59.  
  60. void Tinh(ll u){for(ll i=H; i>=0; i--)push(u>>i);}
  61.  
  62. void Tinh2(ll u){
  63.     while(u>1){
  64.         u/=2;
  65.         tree[u].mx=max(tree[u*2].mx, tree[u*2+1].mx);
  66.         tree[u].mn=min(tree[u*2].mn, tree[u*2+1].mn);
  67.     }
  68. }
  69.  
  70. void update(ll lk, ll rk, ll val){
  71.     lk+=n, rk+=n;
  72.     for(ll l=lk, r=rk; l<=r; l=(l+1)/2, r=(r-1)/2){
  73.         if(l==r)apply(l, val);
  74.         else{
  75.             if(l%2==1)apply(l, val);
  76.             if(r%2==0)apply(r, val);
  77.         }
  78.     }
  79.     Tinh(lk), Tinh(rk);
  80.     Tinh2(lk), Tinh2(rk);
  81. }
  82.  
  83. void change(ll u, ll v, ll val){
  84.     if(par[v]==u)swap(u, v);
  85.     u=pos[u]+n;//cout<<u<<"\n";
  86.     Tinh(u);
  87.     Tinh2(u);
  88.     tree[u].mx=val, tree[u].mn=val;
  89.     Tinh(u);
  90.     Tinh2(u);
  91. }
  92.  
  93. ll get(ll l, ll r){
  94.     l+=n, r+=n;
  95.     Tinh(l), Tinh(r);
  96.     ll ans=-MAX;
  97.     for(; l<=r; l=(l+1)/2, r=(r-1)/2){
  98.         if(l==r)ans=max(ans, tree[l].mx);
  99.         else{
  100.             if(l%2==1)ans=max(ans, tree[l].mx);
  101.             if(r%2==0)ans=max(ans, tree[r].mx);
  102.         }
  103.     }
  104.     return ans;
  105. }
  106.  
  107. ll lcaget(ll u, ll v){
  108.     if(u==v)return 0;
  109.     ll ans=-MAX;
  110.     while(head[u]!=head[v]){
  111.         if(dep[head[u]]<dep[head[v]])swap(u, v);
  112.         ans=max(ans, get(pos[head[u]], pos[u]));
  113.         u=par[head[u]];
  114.     }
  115.  
  116.     if(dep[u]<dep[v])swap(u, v);
  117.     ans=max(ans, get(pos[v]+1, pos[u]));
  118.     return ans;
  119. }
  120.  
  121. void lcaupdate(ll u, ll v, ll val){
  122.     while(head[u]!=head[v]){//cout<<u<<" "<<head[u]<<" "<<v<<" "<<head[v]<<"\n";
  123.         if(dep[head[u]]<dep[head[v]])swap(u, v);
  124.         update(pos[head[u]], pos[u], val);
  125.         u=par[head[u]];
  126.     }
  127.  
  128.     if(dep[u]<dep[v])swap(u, v);
  129.     update(pos[v]+1, pos[u], val);
  130. }
  131.  
  132.  
  133. int main(){
  134.     ios_base::sync_with_stdio(0);
  135.     cin.tie(0);        cout.tie(0);
  136.     if(fopen("Helloworld.inp", "r")){
  137.         freopen("Helloworld.inp", "r", stdin);
  138.         freopen("Helloworld.out", "w", stdout);
  139.     }
  140.  
  141.     cin>>t;
  142.     while(t--){
  143.         cin>>n;
  144.         for(ll i=1; i<=2*n+1; i++)tree[i]={0, MAX, 0};
  145.         for(ll i=1; i<=n; i++)vec[i].clear();
  146.         for(ll i=1; i<=n; i++)heavy[i]=0;
  147.         canh.clear();
  148.         timerHLD=0;
  149.  
  150.         H=__lg(n);
  151.         for(ll i=1, u, v, w; i<n; i++){
  152.             cin>>u>>v>>w;
  153.             vec[u].push_back(v);
  154.             vec[v].push_back(u);
  155.             canh.push_back({u, v, w});
  156.         }
  157.         build(1, 0);
  158.         buildHLD(1, 1);
  159.         for(auto [u, v, w]:canh)change(u, v, w);
  160.  
  161.         string truy;
  162.         for(ll tv=1, i, u, v, val; 1; tv++){
  163.             cin>>truy;
  164. if(truy=="CHANGE")cin>>i>>val, change(canh[i-1].u, canh[i-1].v, val);
  165.             if(truy=="NEGATE")cin>>u>>v, lcaupdate(u, v, 1);
  166.             if(truy=="QUERY")cin>>u>>v, cout<<lcaget(u, v)<<"\n";
  167.             if(truy=="DONE")break;
  168.         }
  169.     }
  170.  
  171.     return 0;
  172. }
  173.  
Success #stdin #stdout 0s 7812KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ytPUXW
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!