fork download
copy 
  1. // ROOT : DRAGON3012009 : Wa In Real Life
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define el "\n"
  5. #define _ROOT_ int main()
  6. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  7. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  8. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  9. #define fi first
  10. #define se second
  11. #define M 1000000007
  12. #define MAXN 200001
  13. #define INF (1ll<<60)
  14. #define NAME "file"
  15. #define debug(a) cerr << #a << " = " << a << endl ;
  16. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  17. using namespace std;
  18. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  19. const ll NMOD = 1;
  20.  
  21. ll n, q ;
  22. ll a[MAXN];
  23. ll st[MAXN ], fin[MAXN ], timeDFS ;
  24. ll chainID[MAXN ], chainHead[MAXN ], curChain  ;
  25. ll sz[MAXN ], bigchild[MAXN ], par[MAXN ] , high[MAXN ] ;
  26. vector<ll> adj[MAXN ] ;
  27.  
  28. struct Node
  29. {
  30.     ll res, pre, suf, sum, trash ;
  31. };
  32.  
  33.  
  34.  
  35. Node MergeNode(Node a, Node b )
  36. {
  37.     if(a.trash ) return b ;
  38.     if(b.trash ) return a ;
  39.     Node res ;
  40.     res.sum = a.sum + b.sum ;
  41.     res.pre = max(a.pre, a.sum + b.pre ) ;
  42.     res.suf = max(b.suf, a.suf + b.sum ) ;
  43.     res.trash = 0 ;
  44.     res.res = max({a.res, b.res, a.suf + b.pre, a.sum + b.pre, a.suf + b.sum }) ;
  45.     return res ;
  46. }
  47.  
  48. struct Seg
  49. {
  50.     Node val[MAXN << 2 ] ;
  51.     void update(ll id, ll l, ll r, ll pos, ll value )
  52.     {
  53.         if(l == r)
  54.         {
  55.             ll nv = max(0LL, value ) ;
  56.             val[id] = {nv, nv, nv, value, 0 } ;
  57.         }
  58.         else
  59.         {
  60.             ll m = l + r >> 1 ;
  61.             if(m >= pos ) update(id << 1, l, m, pos, value ) ;
  62.             else update(id << 1 | 1, m + 1, r,  pos, value ) ;
  63.             val[id] = MergeNode(val[id << 1], val[id << 1 | 1 ]) ;
  64.         }
  65.     }
  66.     Node get(ll id, ll l, ll r, ll u, ll v )
  67.     {
  68.         if(u > r || v < l ) return {1, 1, 1, 1, 1 } ;
  69.         if(u <= l && v >= r ) return val[id] ;
  70.         ll m = l + r >> 1 ;
  71.         return MergeNode(get(id << 1, l, m, u, v ), get(id << 1 | 1, m + 1, r, u, v )) ;
  72.     }
  73. } seg ;
  74.  
  75. void hld(ll u, ll p )
  76. {
  77.     if(!chainHead[curChain ]) chainHead[curChain ] = u ;
  78.     chainID[u] = curChain ;
  79.     st[u] = ++timeDFS ;
  80.     if(bigchild[u] != 0 ) hld(bigchild[u] , u ) ;
  81.  
  82.     for(ll v : adj[u] ) if(v != p && v != bigchild[u]) {
  83.         curChain ++ ;
  84.         hld(v , u   ) ;
  85.     }
  86.  
  87.     fin[u] = timeDFS ;
  88. }
  89.  
  90. ll LCA(ll u , ll v ) {
  91. //    debug(u) ;
  92. while(chainID[u] != chainID[v]) {
  93.     if(chainID[u] > chainID[v]) u = par[chainHead[chainID[u]]] ;
  94.     else v = par[chainHead[chainID[v]]] ;
  95. //    debug(u ) ;
  96. //    debug(v ) ;
  97. }
  98. if(high[u] > high[v]) swap(u , v ) ;
  99. return u ;
  100. }
  101.  
  102. Node get_path(ll u , ll v ) {
  103.     ll lca = LCA(u , v ) ;
  104.     Node res ;
  105.     res.trash = true ;
  106.     vector<Node> L , R ;
  107.  
  108.     while(chainID[u] != chainID[lca ]) {
  109.         L.push_back(seg.get(1 , 1 , n , st[chainHead[chainID[u]]] , st[u] )) ;
  110.         u = par[chainHead[chainID[u]]] ;
  111. //        debug(u) ;
  112.     }
  113.  
  114.     while(chainID[v] != chainID[lca ]) {
  115.         R.push_back(seg.get(1 , 1 , n , st[chainHead[chainID[v]]] , st[v] )) ;
  116.         v = par[chainHead[chainID[v]]] ;
  117.     }
  118.  
  119.     if(high[u] <= high[v] ) R.push_back(seg.get(1 , 1 , n , st[u] , st[v]) ) ;
  120.     if(high[u] > high[v] ) L.push_back(seg.get(1 , 1 , n , st[v] , st[u]) ) ;
  121.     for(Node & it : L ) {
  122.         swap(it.pre , it.suf ) ;
  123.     }
  124.     for(Node & it : L ) res = MergeNode(res , it ) ;
  125.     reverse(R.begin() , R.end() ) ;
  126.     for(Node & it : R ) res = MergeNode(res , it ) ;
  127.     return res ;
  128. }
  129.  
  130. void dfs(ll u, ll p )
  131. {
  132.     sz[u] = 1 ;
  133.     ll ma = 0 ;
  134.     for(ll v : adj[u]) if(v != p )
  135.         {
  136.             high[v] = high[u  ] + 1  ;
  137.             par[v] = u ;
  138.             dfs(v, u ) ;
  139.             sz[u] += sz[v] ;
  140.             if(ma == 0 || sz[ma] < sz[v]) ma = v ;
  141.         }
  142.     bigchild[u] = ma ;
  143. }
  144.  
  145. void init()
  146. {
  147.     cin >> n >> q ;
  148.     FOR(i, 1, n ) cin >> a[i] ;
  149.     FOR(i, 2, n )
  150.     {
  151.         ll x, y ;
  152.         cin >> x >> y ;
  153.         adj[x].push_back(y) ;
  154.         adj[y].push_back(x) ;
  155.     }
  156.     dfs(1, 1 ) ;
  157.     hld(1, 1  ) ;
  158.     FOR(i, 1, n ) seg.update(1, 1, n, st[i], a[i]) ;
  159. }
  160.  
  161. void solve()
  162. {
  163.     FOR(cnt , 1 , q ) {
  164.     ll t , l , r ; cin >> t >> l >> r ;
  165.     if(t == 1 ) seg.update(1 , 1 , n , st[l] , r ) ;
  166.     else {
  167.         Node res = get_path(l , r ) ;
  168.         cout << res.res << el ;
  169.     }
  170.     }
  171. }
  172.  
  173. _ROOT_
  174. {
  175.     // freopen(NAME".inp" , "r" , stdin);
  176.     // freopen(NAME".out" , "w", stdout) ;
  177.     ios_base::sync_with_stdio(0);
  178.     cin.tie(0);
  179.     cout.tie(0);
  180.     int t = 1; // cin >> t ;
  181.     while(t--)
  182.     {
  183.         init();
  184.         solve();
  185.     }
  186.     return (0&0);
  187. }
  188.  
Success #stdin #stdout 0.01s 15912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NyjlaE
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!