fork download
copy 
  1. /// Link:
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. bool M1;
  6. //#define int long long
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. #define eb emplace_back
  11. #define il pair<ll,ll>
  12. #define ii pair<int,int>
  13. #define len(s) (int)s.size()
  14. #define all(s) (s).begin(),(s).end()
  15. #define OpenFile(Name) if (fopen(Name".inp","r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
  16.  
  17. #define MASK(x) ((1LL)<<(x))
  18. #define Bit(x,i) (((x)>>(i))&1)
  19. #define Countbit(x) __builtin_popcountll(x)
  20.  
  21. typedef long long ll;
  22. typedef long double ld;
  23.  
  24. int dx[]={1,-1,0,0,-1,1,1,-1};
  25. int dy[]={0,0,1,-1,-1,-1,1,1};
  26.  
  27. template <class T> bool Minimize(T &a,T b) { if (a>b) { a=b; return true; } return false;}
  28. template <class T> bool Maximize(T &a,T b) { if (a<b) { a=b; return true; } return false;}
  29.  
  30. inline ll add(ll a,ll b,ll c) { return (a+b)%c; };
  31. inline ll sub(ll a,ll b,ll c) { return (a-b+c)%c; };
  32. inline ll mul(ll a,ll b,ll c) { return ((a%c)*(b%c))%c; };
  33.  
  34. const int N=1e5+5,M=1e3+5,INF=1e9,lim=1e6;
  35. const int block=448,base=256;
  36.  
  37. ll Mod=1e9+7,Mod_base=1777777777,LNF=1e18;
  38.  
  39. ///________________________________________________________________________________________________________
  40.  
  41. int n,q;
  42. vector<int> g[N];
  43. int gt[N],timer=0;
  44. int tin[N],tout[N],sz[N],heavy[N],head[N],h[N],par[N];
  45.  
  46. void DFS(int u=1,int p=0) {
  47.     sz[u]=1;
  48.     for (int v:g[u])
  49.     if (v!=p) {
  50.         h[v]=h[u]+1;
  51.         par[v]=u;
  52.         DFS(v,u);
  53.         sz[u]+=sz[v];
  54.         if (sz[v]>sz[heavy[u]]) heavy[u]=v;
  55.     }
  56. }
  57.  
  58. void HLD(int u=1,int p=1) {
  59.     tin[u]=++timer;
  60.     head[u]=p;
  61.     if (heavy[u]) HLD(heavy[u],p);
  62.     for (int v:g[u])
  63.     if (v!=par[u] && v!=heavy[u]) HLD(v,v);
  64. }
  65.  
  66. struct seg {
  67.     ll sum,pre,suf,best;
  68.     seg() {
  69.         sum=0;
  70.         pre=suf=best=0;
  71.     }
  72. };
  73.  
  74. seg combine(seg a,seg b) {
  75.     seg res;
  76.     res.sum=a.sum+b.sum;
  77.     res.pre=max(a.pre,a.sum+b.pre);
  78.     res.suf=max(b.suf,b.sum+a.suf);
  79.     res.best=max(max(a.best,b.best),a.suf+b.pre);
  80.     return res;
  81. }
  82.  
  83. ll lazy[4*N];
  84. seg t[4*N];
  85.  
  86. void apply(int i,int l,int r,ll val) {
  87.     t[i].sum=(r-l+1)*val;
  88.     lazy[i]=val;
  89.     t[i].pre=t[i].suf=t[i].best=max(0LL,t[i].sum);
  90. }
  91.  
  92. void Push(int i,int l,int r) {
  93.     if (lazy[i]==-1) return ;
  94.     int m=(l+r)>>1;
  95.     apply(i<<1,l,m,lazy[i]);
  96.     apply(i<<1|1,m+1,r,lazy[i]);
  97.     lazy[i]=-1;
  98. }
  99.  
  100. void upd(int i,int l,int r,int u,int v,ll val) {
  101.     if (v<l || r<u) return ;
  102.     if (u<=l && r<=v) {
  103.         apply(i,l,r,val);
  104.         return ;
  105.     }
  106.     Push(i,l,r);
  107.     int m=(l+r)>>1;
  108.     upd(i<<1,l,m,u,v,val);
  109.     upd(i<<1|1,m+1,r,u,v,val);
  110.     t[i]=combine(t[i<<1],t[i<<1|1]);
  111. }
  112.  
  113. seg get(int i,int l,int r,int u,int v) {
  114.     if (v<l || r<u) return seg();
  115.     if (u<=l && r<=v) return t[i];
  116.     Push(i,l,r);
  117.     int m=(l+r)>>1;
  118.     return combine(get(i<<1,l,m,u,v),get(i<<1|1,m+1,r,u,v));
  119. }
  120.  
  121. void upd_path(int u,int v,ll val) {
  122.     while (head[u]!=head[v]) {
  123.         if (h[head[u]]<h[head[v]]) swap(u,v);
  124.         upd(1,1,n,tin[head[u]],tin[u],val);
  125.         u=par[head[u]];
  126.     }
  127.     if (h[u]>h[v]) swap(u,v);
  128.     upd(1,1,n,tin[u],tin[v],val);
  129. }
  130.  
  131. ll get_path(int u,int v) {
  132.     seg l,r;
  133.     while (head[u]!=head[v]) {
  134.         if (h[head[u]]<h[head[v]]) {
  135.             r=combine(get(1,1,n,tin[head[v]],tin[v]),r);
  136.             v=par[head[v]];
  137.         } else {
  138.             l=combine(get(1,1,n,tin[head[u]],tin[u]),l);
  139.             u=par[head[u]];
  140.         }
  141.     }
  142.     if (h[u]>h[v]) l=combine(get(1,1,n,tin[v],tin[u]),l); else
  143.                    r=combine(get(1,1,n,tin[u],tin[v]),r);
  144.     return max(max(l.best,r.best),l.pre+r.pre);
  145. }
  146.  
  147. bool M2;
  148. signed main() {
  149.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  150.     OpenFile("TASK");
  151.  
  152.     cin>>n;
  153.     for (int i=1;i<=n;++i) cin>>gt[i];
  154.     for (int i=1;i<n;++i) {
  155.         int u,v; cin>>u>>v;
  156.         g[u].eb(v);
  157.         g[v].eb(u);
  158.     }
  159.  
  160.     DFS();
  161.     HLD();
  162.     memset(lazy,-1,sizeof lazy);
  163.  
  164.     for (int i=1;i<=n;++i) upd(1,1,n,tin[i],tin[i],gt[i]);
  165.     int q; cin>>q;
  166.     while (q--) {
  167.         int op,a,b,c; cin>>op>>a>>b;
  168.         if (op==1) cout<<get_path(a,b)<<'\n'; else {
  169.             cin>>c;
  170.             upd_path(a,b,c);
  171.         }
  172.     }
  173.  
  174.  
  175.     cerr<<"Time: "<<(1.0*clock()/CLOCKS_PER_SEC)<<" s\n";
  176.     cerr<<"Memory: "<<abs(&M2-&M1)/1024.0/1024<<" MB\n";
  177.     return 0;
  178. }
  179.  
Success #stdin #stdout #stderr 0.01s 24832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time: 0.008934 s
Memory: 20.6005 MB
https://ideone.com/o3w8DZ
language:
C++14 (clang 8.0)
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!