fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
  5. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  6. #define sz(a) (int)(a).size()
  7. #define all(a) (a).begin(), (a).end()
  8. #define bit(s, i) (((s) >> (i)) & 1)
  9. #define ii pair <int, int>
  10. #define pll pair<ll,ll>
  11. #define fi first
  12. #define se second
  13. #define ll long long
  14. #define eb emplace_back
  15. #define pb push_back
  16. #define __builtin_popcount __builtin_popcountll
  17.  
  18. template <class X, class Y>
  19.     bool maxi(X &x, Y y) {
  20.         if(x < y) {
  21.             x = y;
  22.             return true;
  23.         }
  24.         return false;
  25.     }
  26.  
  27. template <class X, class Y>
  28.     bool mini(X &x, Y y) {
  29.         if(x > y) {
  30.             x = y;
  31.             return true;
  32.         }
  33.         return false;
  34.     }
  35.  
  36. void solve();
  37. int32_t main() {
  38.     #define task "test"
  39.     if(fopen(task".inp", "r")){
  40.         freopen(task".inp", "r", stdin);
  41.         freopen(task".out", "w", stdout);
  42.     }
  43.     cin.tie(0)->sync_with_stdio(0);
  44.  
  45.     int tc = 1; //cin >> tc;
  46.     FOR(i, 1, tc){
  47.         solve();
  48.     }
  49. }
  50.  
  51. const int N=2e5+5;
  52.  
  53. int n,q,we[N],tin[N],tout[N],tour[N*2],Time,up[N][18]; ll d[N];
  54. vector<ii> adj[N];
  55. ii edge[N];
  56.  
  57. struct Node{
  58.     ll mx,mi,lz,best1,best2; bool turn;
  59.     Node(){
  60.         mx=-1e18; mi=1e18; lz=0; turn=0;
  61.         best1=best2=-1e18;
  62.     }
  63. } st[N*8];
  64.  
  65. void dfs(int u, int p){
  66.     tin[u]=++Time; tour[Time]=u;
  67.     for(auto [v,w]:adj[u]) if(v!=p){
  68.         d[v]=d[u]+w;
  69.         up[v][0]=u;
  70.         FOR(i,1,17) up[v][i]=up[up[v][i-1]][i-1];
  71.         dfs(v,u);
  72.         tour[++Time]=u;
  73.     }
  74.     tout[u]=Time;
  75. }
  76.  
  77. void combine(Node &c, Node &a, Node &b){
  78.     c.mx=-1e18, c.mi=1e18;
  79.     c.best1=c.best2=-1e18;
  80.     if(a.turn) maxi(c.mx,a.mx), mini(c.mi,a.mi), maxi(c.best1,a.best1), maxi(c.best2,a.best2);
  81.     if(b.turn) maxi(c.mx,b.mx), mini(c.mi,b.mi), maxi(c.best1,b.best1), maxi(c.best2,b.best2);
  82.     if(a.turn&&b.turn){
  83.         maxi(c.best1,a.mx-2*b.mi);
  84.         maxi(c.best2,b.mx-2*a.mi);
  85.     }
  86. }
  87.  
  88. void build(int id, int l, int r){
  89.     st[id].turn=1;
  90.     if(l==r){
  91.         st[id].mx=st[id].mi=d[tour[l]];
  92.         st[id].best1=st[id].best2=-d[tour[l]];
  93.         return;
  94.     }
  95.     int mid=(l+r)>>1;
  96.     build(id<<1,l,mid);
  97.     build(id<<1|1,mid+1,r);
  98.     combine(st[id],st[id<<1],st[id<<1|1]);
  99. }
  100.  
  101. void apply_add(int id, ll val){
  102.     st[id].mi+=val;
  103.     st[id].mx+=val;
  104.     st[id].lz+=val;
  105.     st[id].best1-=val;
  106.     st[id].best2-=val;
  107. }
  108. void down(int id){
  109.     if(st[id].lz==0) return;
  110.     apply_add(id<<1,st[id].lz);
  111.     apply_add(id<<1|1,st[id].lz);
  112.     st[id].lz=0;
  113. }
  114.  
  115. void upd_del(int u, int v, int val, int id, int l, int r){
  116.     if(u>r||v<l) return;
  117.     if(u<=l&&r<=v){
  118. //            cout<<l<<" "<<r<<" "<<id<<" "<<val<<'\n';
  119.         st[id].turn=val;
  120.         return;
  121.     }
  122.     int mid=(l+r)>>1;
  123.     down(id);
  124.     upd_del(u,v,val,id<<1,l,mid);
  125.     upd_del(u,v,val,id<<1|1,mid+1,r);
  126.     combine(st[id],st[id<<1],st[id<<1|1]);
  127. }
  128.  
  129. void upd_add(int u, int v, ll val, int id, int l, int r){
  130.     if(u>r||v<l) return;
  131.     if(u<=l&&r<=v){
  132.         apply_add(id,val);
  133.         return;
  134.     }
  135.     int mid=(l+r)>>1;
  136.     down(id);
  137.     upd_add(u,v,val,id<<1,l,mid);
  138.     upd_add(u,v,val,id<<1|1,mid+1,r);
  139.     combine(st[id],st[id<<1],st[id<<1|1]);
  140. }
  141.  
  142. Node get(int u, int v, int id, int l, int r){
  143. //    cout<<l<<" "<<r<<" "<<id<<" "<<st[id].turn<<'\n';
  144.     if(!st[id].turn) return Node();
  145.     if(u<=l&&r<=v){
  146.         return st[id];
  147.     }
  148.     int mid=(l+r)>>1;
  149.     down(id);
  150.     if(u>mid) return get(u,v,id<<1|1,mid+1,r);
  151.     if(v<=mid) return get(u,v,id<<1,l,mid);
  152.     Node c; c.turn=1;
  153.     Node a=get(u,v,id<<1,l,mid), b=get(u,v,id<<1|1,mid+1,r);
  154.     combine(c,a,b);
  155.     return c;
  156. }
  157.  
  158. void solve() {
  159.     cin>>n;
  160.     FOR(i,1,n-1){
  161.         int u,v,w; cin>>u>>v>>w;
  162.         adj[u].eb(v,w); adj[v].eb(u,w);
  163.         we[i]=w;
  164.         edge[i]={u,v};
  165.     }
  166.     dfs(1,1);
  167.  
  168. //    FOR(i,1,Time) cout<<tour[i]<<" ";
  169.  
  170.     build(1,1,Time);
  171.     cin>>q;
  172.     FOR(_,1,q){
  173.         int t; cin>>t;
  174.         if(t==1){
  175.             int x,k;
  176.             vector<int> ds;
  177.  
  178.             cin>>x>>k;
  179.             FOR(i,1,k){
  180.                 int p; cin>>p;
  181.                 ds.eb(p);
  182.             }
  183.  
  184.             vector<ii> it;
  185.             for(int p:ds){
  186.                 if(tin[p]<=tin[x]&&tout[x]<=tout[p]) {
  187.                     int c=x;
  188.                     FORD(i,17,0) if(d[up[c][i]]>d[p]) c=up[c][i];
  189.                     if(1<=tin[c]-1) it.eb(1,tin[c]-1);
  190.                     if(tout[c]+1<=Time) it.eb(tout[c]+1,Time);
  191.                 }
  192.                 else it.eb(tin[p],tout[p]);
  193.             }
  194.  
  195.             for(auto [l,r]:it){
  196. //                cout<<l<<" "<<r<<'\n';
  197.                 upd_del(l,r,0,1,1,Time);
  198.             }
  199.  
  200.             ll dep=get(tin[x],tin[x],1,1,Time).mi;
  201. //            cout<<get(1,tin[x],1,1,Time).best1<<'\n';
  202.             cout<<max({0ll,max(get(1,tin[x],1,1,Time).best1,get(tin[x],Time,1,1,Time).best2)+dep})<<'\n';
  203.  
  204.             for(auto [l,r]:it){
  205.                 upd_del(l,r,1,1,1,Time);
  206.             }
  207.         }
  208.         else{
  209.             int i,w; cin>>i>>w;
  210.             if(tin[edge[i].fi]>tin[edge[i].se]) swap(edge[i].fi,edge[i].se);
  211.             upd_add(tin[edge[i].se],tout[edge[i].se],w-we[i],1,1,Time);
  212.             we[i]=w;
  213.         }
  214.     }
  215.  
  216. }
  217.  
Success #stdin #stdout 0.02s 87856KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BW3s7r
language:
C++ (gcc 8.3)
created:
5 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!