fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5. const long long oo=1e9;
  6. const int mod=1e9+7;
  7. const int base=31;
  8. int Test=1;
  9. void home()
  10. {
  11.     if(fopen("main.inp","r")) 
  12.     freopen("main.inp","r",stdin),
  13.     freopen("main.out","w",stdout);
  14. }
  15. bool bit(int mask,int i){return (mask>>i)&1;}
  16. struct Node{int gss,maL,maR,sum;};
  17. Node Merge(Node a,Node b)
  18. {
  19.     Node c;
  20.     c.gss=max(max(a.gss,b.gss),a.maR+b.maL);
  21.     c.maL=max(a.maL,a.sum+b.maL);
  22.     c.maR=max(b.maR,b.sum+a.maR);
  23.     c.sum=a.sum+b.sum;
  24.     return c;
  25. }
  26. struct SegTree
  27. {
  28.     int n;vector<Node>f;vector<int>lazy;
  29.     SegTree(int _n):n(_n){f.resize(4*n+5);lazy.resize(4*n+5,-oo);}
  30.     void Push(int id,int l,int r,int val)
  31.     {
  32.         int gss=max(0,(r-l+1)*val);
  33.         f[id]={gss,gss,gss,(r-l+1)*val};
  34.         lazy[id]=val;
  35.     }
  36.     void Fix(int id,int l,int r)
  37.     {
  38.         if(lazy[id]!=-oo)
  39.         {
  40.             int m=(l+r)>>1;
  41.             Push(id<<1,l,m,lazy[id]);
  42.             Push(id<<1|1,m+1,r,lazy[id]);
  43.             lazy[id]=-oo;
  44.         }
  45.     }
  46.     void Update(int id,int l,int r,int u,int v,int val)
  47.     {
  48.         if(u>v)return;
  49.         if(l==u&&r==v)Push(id,l,r,val);
  50.         else 
  51.         {
  52.             Fix(id,l,r);int m=(l+r)>>1;
  53.             Update(id<<1,l,m,u,min(v,m),val);
  54.             Update(id<<1|1,m+1,r,max(m+1,u),v,val);
  55.             f[id]=Merge(f[id<<1],f[id<<1|1]);
  56.         }
  57.     }
  58.     Node Get(int id,int l,int r,int u,int v)
  59.     {
  60.         if(u>v)return {0,0,0,0};
  61.         if(l==u&&r==v)return f[id];
  62.         else
  63.         {
  64.             Fix(id,l,r);int m=(l+r)>>1;
  65.             return Merge(Get(id<<1,l,m,u,min(v,m)),Get(id<<1|1,m+1,r,max(m+1,u),v));
  66.         }
  67.     }
  68.     void Update(int u,int v,int val){Update(1,1,n,u,v,val);}
  69.     Node Get(int u,int v){return Get(1,1,n,u,v);}
  70. }*Seg;
  71. int n,q;
  72. int val[100005],sau[100005],par[100005],pos[100005],sz[100005];
  73. int ChHd[100005],ChId[100005];
  74. vector<int>a[100005];
  75. void DFS(int u)
  76. {
  77.     sz[u]=1;
  78.     for(int v:a[u])
  79.     {
  80.         if(v!=par[u])
  81.         {
  82.             par[v]=u;sau[v]=sau[u]+1;
  83.             DFS(v);sz[u]+=sz[v];
  84.         }
  85.     }
  86. }
  87. int CurPos,CurCh=1;
  88. void HLD(int u)
  89. {
  90.     if(!ChHd[CurCh])ChHd[CurCh]=u;
  91.     ChId[u]=CurCh;
  92.     pos[u]=++CurPos;
  93.     int hev=0;for(int v:a[u])if(v!=par[u])if(!hev||sz[hev]<sz[v])hev=v;
  94.     if(hev)HLD(hev);
  95.     for(int v:a[u])
  96.     {
  97.         if(v!=par[u]&&v!=hev)
  98.         {
  99.             CurCh++;
  100.             HLD(v);
  101.         }
  102.     }
  103. }
  104. int LCA(int u,int v)
  105. {
  106.     while(ChId[u]!=ChId[v])
  107.     {
  108.         if(ChId[u]>ChId[v])u=par[ChHd[ChId[u]]];
  109.         else v=par[ChHd[ChId[v]]];
  110.     }
  111.     if(sau[u]>sau[v])return v;
  112.     return u;
  113. }
  114. Node Rev(Node a)
  115. {
  116.     return {a.gss,a.maR,a.maL,a.sum};
  117. }
  118. int PathQuery(int u,int v)
  119. {
  120.     int w=LCA(u,v);Node ma={0,0,0,0};
  121.     while(ChId[u]!=ChId[w])
  122.     {
  123.         ma=Merge(ma,Rev(Seg->Get(pos[ChHd[ChId[u]]],pos[u])));
  124.         u=par[ChHd[ChId[u]]];
  125.     }
  126.     vector<Node>vec;
  127.     while(ChId[v]!=ChId[w])
  128.     {
  129.         vec.push_back(Seg->Get(pos[ChHd[ChId[v]]],pos[v]));
  130.         v=par[ChHd[ChId[v]]];
  131.     }
  132.     if(sau[u]>sau[v])
  133.     {
  134.         ma=Merge(ma,Rev(Seg->Get(pos[v],pos[u])));
  135.     }
  136.     else 
  137.     {
  138.         vec.push_back(Seg->Get(pos[u],pos[v]));
  139.     }
  140.     reverse(vec.begin(),vec.end());
  141.     for(Node x:vec)ma=Merge(ma,x);
  142.     return ma.gss;
  143. }
  144. void PathUpdate(int u,int v,int x)
  145. {
  146.     int w=LCA(u,v);
  147.     while(ChId[u]!=ChId[w])
  148.     {
  149.         Seg->Update(pos[ChHd[ChId[u]]],pos[u],x);
  150.         u=par[ChHd[ChId[u]]];
  151.     }
  152.     while(ChId[v]!=ChId[w])
  153.     {
  154.         Seg->Update(pos[ChHd[ChId[v]]],pos[v],x);
  155.         v=par[ChHd[ChId[v]]];
  156.     }
  157.     if(sau[u]>sau[v])swap(u,v);
  158.     Seg->Update(pos[u],pos[v],x);
  159. }
  160. void Tcmduc_VOI26()
  161. {
  162.     cin>>n>>q;Seg=new SegTree(n);
  163.     for(int i=1;i<=n;i++)cin>>val[i];
  164.     for(int i=1;i<n;i++)
  165.     {
  166.         int u,v;cin>>u>>v;
  167.         a[u].push_back(v);
  168.         a[v].push_back(u);
  169.     }
  170.     DFS(1);HLD(1);
  171.     for(int i=1;i<=n;i++)Seg->Update(pos[i],pos[i],val[i]);
  172.     while(q--)
  173.     {
  174.         int type,u,v;cin>>type>>u>>v;
  175.         if(type==2)
  176.         {
  177.             int x;cin>>x;
  178.             PathUpdate(u,v,x);
  179.         }
  180.         else cout<<PathQuery(u,v)<<'\n';
  181.     }
  182. }
  183. signed main()
  184. {
  185.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  186.     while(Test--)Tcmduc_VOI26();
  187.     return 0;
  188. }
Success #stdin #stdout 0.01s 7048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vnccva
language:
C++14 (gcc 8.3)
created:
12 hours 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!