Advertisement
konchin_shih

Heavy-light Decomposition

Sep 27th, 2022
1,110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<functional>
  5. #include<random>
  6. #define endl '\n'
  7. using namespace std;
  8. using ll=long long;
  9. template<typename T> using V=vector<T>;
  10. template<typename T> using F=function<T>;
  11. template<typename T1,typename T2=T1> using P=pair<T1,T2>;
  12. mt19937 mt(hash<string>()(":poop:"));
  13. constexpr int maxn=2e5+5;
  14. int arr[(maxn+1)<<2];
  15. #define m ((l+r)>>1)
  16. void build(V<int>& v,int i=1,int l=0,int r=maxn){
  17.     if((int)v.size()<=l) return;
  18.     if(r-l==1){arr[i]=v[l];return;}
  19.     build(v,i<<1,l,m),build(v,i<<1|1,m,r);
  20.     arr[i]=max(arr[i<<1],arr[i<<1|1]);
  21. }
  22. void modify(int p,int k,int i=1,int l=0,int r=maxn){
  23.     if(p<l||r<=p) return;
  24.     if(r-l==1){arr[i]=k;return;}
  25.     if(p<m) modify(p,k,i<<1,l,m);
  26.     else modify(p,k,i<<1|1,m,r);
  27.     arr[i]=max(arr[i<<1],arr[i<<1|1]);
  28. }
  29. int query(int ql,int qr,int i=1,int l=0,int r=maxn){
  30.     if(qr<=l||r<=ql) return 0;
  31.     if(ql<=l&&r<=qr) return arr[i];
  32.     if(qr<=m) return query(ql,qr,i<<1,l,m);
  33.     if(m<=ql) return query(ql,qr,i<<1|1,m,r);
  34.     return max(query(ql,qr,i<<1,l,m),query(ql,qr,i<<1|1,m,r));
  35. }
  36. #undef m
  37. inline void solve(){
  38.     int n,q;cin>>n>>q;
  39.     V<int> v(n);
  40.     for(auto& i:v)
  41.         cin>>i;
  42.     V<V<int>> e(n);
  43.     for(int i=1;i<n;i++){
  44.         int a,b;cin>>a>>b,a--,b--;
  45.         e[a].emplace_back(b);
  46.         e[b].emplace_back(a);
  47.     }
  48.     V<int> d(n,0),f(n,0),sz(n,1),son(n,-1);
  49.     F<void(int,int)> dfs1=
  50.     [&](int x,int pre){
  51.         for(auto i:e[x]) if(i!=pre){
  52.             d[i]=d[x]+1,f[i]=x;
  53.             dfs1(i,x),sz[x]+=sz[i];
  54.             if(!~son[x]||sz[son[x]]<sz[i])
  55.                 son[x]=i;
  56.         }
  57.     };dfs1(0,0);
  58.     V<int> top(n,0),dfn(n,-1),rnk(n,0);
  59.     F<void(int,int)> dfs2=
  60.     [&](int x,int t){
  61.         static int cnt=0;
  62.         dfn[x]=cnt++,rnk[dfn[x]]=x,top[x]=t;
  63.         if(!~son[x]) return;
  64.         dfs2(son[x],t);
  65.         for(auto i:e[x])
  66.             if(!~dfn[i]) dfs2(i,i);
  67.     };dfs2(0,0);
  68.     V<int> dfnv(n);
  69.     for(int i=0;i<n;i++)
  70.         dfnv[dfn[i]]=v[i];
  71.     build(dfnv);
  72.     while(q--){
  73.         int op,a,b;cin>>op>>a>>b;
  74.         switch(op){
  75.         case 1:{
  76.             modify(dfn[a-1],b);
  77.         }break;
  78.         case 2:{
  79.             a--,b--;
  80.             int ans=0;
  81.             while(top[a]!=top[b]){
  82.                 if(d[top[a]]>d[top[b]]) swap(a,b);
  83.                 ans=max(ans,query(dfn[top[b]],dfn[b]+1));
  84.                 b=f[top[b]];
  85.             }
  86.             if(dfn[a]>dfn[b]) swap(a,b);
  87.             ans=max(ans,query(dfn[a],dfn[b]+1));
  88.             cout<<ans<<endl;
  89.         }break;
  90.         }
  91.     }
  92. }
  93. int main(){
  94.     cin.tie(nullptr);
  95.     ios::sync_with_stdio(false);
  96.     solve();
  97.     return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement