#448476 (C++17) No.899 γatheree

• 問題: No.899 γatheree
• ユーザー: beet
• 提出日時: 2020-03-23 23:41:01
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,373 ms / 2,000 ms
• コード長: 7,841 bytes
• コンパイル時間: 3,861 ms
• コンパイル使用メモリ: 216,708 KB
• 最終ジャッジ日時: 2025-01-09 09:57:48
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
sample	AC * 1
other	AC * 23

ソースコード

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct LevelAncestor{
  int n,h;
  vector<vector<int> > G,par,lad;
  vector<int> dep,nxt,len,pth,ord,hs;
  LevelAncestor(){}
  LevelAncestor(int n):
    n(n),G(n),dep(n),nxt(n,-1),len(n),pth(n),ord(n),hs(n+1,0){
    h=1;
    while((1<<h)<=n) h++;
    par.assign(h,vector<int>(n,-1));
    for(int i=2;i<=n;i++) hs[i]=hs[i>>1]+1;
  }

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(int v,int p,int d,int f){
    if(nxt[v]<0){
      par[0][nxt[v]=v]=p;
      len[v]=dep[v]=d;
      for(int u:G[v]){
        if(u==p) continue;
        dfs(u,v,d+1,0);
        if(len[v]<len[u]) nxt[v]=u,len[v]=len[u];
      }
    }
    if(!f) return;
    pth[v]=lad.size();
    lad.emplace_back();
    for(int k=v;;k=nxt[k]){
      lad.back().emplace_back(k);
      pth[k]=pth[v];
      if(k==nxt[k]) break;
    }
    for(;;p=v,v=nxt[v]){
      for(int u:G[v])
        if(u!=p&&u!=nxt[v]) dfs(u,v,d+1,1);
      if(v==nxt[v]) break;
    }
  }

  void build(int r=0){
    dfs(r,-1,0,1);
    for(int k=0;k+1<h;k++){
      for(int v=0;v<n;v++){
        if(par[k][v]<0) par[k+1][v]=-1;
        else par[k+1][v]=par[k][par[k][v]];
      }
    }
    for(int i=0;i<(int)lad.size();i++){
      int v=lad[i][0],p=par[0][v];
      if(~p){
        int k=pth[p],l=min(ord[p]+1,(int)lad[i].size());
        lad[i].resize(l+lad[i].size());
        for(int j=0,m=lad[i].size();j+l<m;j++)
          lad[i][m-(j+1)]=lad[i][m-(j+l+1)];
        for(int j=0;j<l;j++)
          lad[i][j]=lad[k][ord[p]-l+j+1];
      }
      for(int j=0;j<(int)lad[i].size();j++)
        if(pth[lad[i][j]]==i) ord[lad[i][j]]=j;
    }
  }

  int lca(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    for(int k=0;k<h;k++){
      if((dep[v]-dep[u])>>k&1){
        v=par[k][v];
      }
    }
    if(u==v) return u;
    for(int k=h-1;k>=0;k--){
      if(par[k][u]!=par[k][v]){
        u=par[k][u];
        v=par[k][v];
      }
    }
    return par[0][u];
  }

  int up(int v,int d){
    if(d==0) return v;
    v=par[hs[d]][v];
    d-=1LL<<hs[d];
    return lad[pth[v]][ord[v]-d];
  }

  int distance(int u,int v){
    return dep[u]+dep[v]-dep[lca(u,v)]*2;
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#undef call_from_test

#endif

//BEGIN CUT HERE
struct EulerTourForBFS : LevelAncestor{
  using super = LevelAncestor;
  vector<int> ls;
  vector<vector<int>> H;
  EulerTourForBFS(int n):super(n),ls(n),H(n){}

  using super::par;
  using super::dep;
  void build(int r=0){
    super::build(r);
    int pos=0;
    queue<int> que;
    que.emplace(r);
    while(!que.empty()){
      int v=que.front();que.pop();
      ls[v]=pos++;
      H[dep[v]].emplace_back(v);
      for(int u:super::G[v]){
        if(u==par[0][v]) continue;
        que.emplace(u);
      }
    }
  }

  int idx(int v){return ls[v];}

  int find(int v,int d,int a){
    int l=-1,r=H[d].size();
    while(l+1<r){
      int m=(l+r)>>1;
      int p=super::up(H[d][m],d-dep[v]);
      if(ls[v]+a<=ls[p]) r=m;
      else l=m;
    }
    return ls[H[d][0]]+r;
  }

  template<typename F>
  void exec(int v,int d,F f){
    if(dep[v]+d>=n or H[dep[v]+d].empty()) return;
    int l=find(v,dep[v]+d,0);
    int r=find(v,dep[v]+d,1);
    if(l<r) f(l,r);
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){}

  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }

  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }

  inline T reflect(int k){
    return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
  }

  inline void propagate(int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }

  inline void thrust(int k){
    for(int i=height;i;i--) propagate(k>>i);
  }

  inline void recalc(int k){
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }

  void update(int a,int b,E x){
    if(a>=b) return;
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
    recalc(a);
    recalc(b);
  }

  void set_val(int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }

  T query(int a,int b){
    if(a>=b) return ti;
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){
    if(l+1==r){
      acc=f(acc,reflect(k));
      return check(acc)?k-n:-1;
    }
    propagate(k);
    int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }

  template<typename C>
  int find(int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};
//END CUT HERE
#ifndef call_from_test

signed CFR569_C(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  vector<int> as(n),bs(m);
  for(int i=0;i<n;i++) cin>>as[i];
  for(int i=0;i<m;i++) cin>>bs[i];

  auto f=[](int a,int b){return max(a,b);};
  auto g=[](int a,int b){return a+b;};
  int ti=0,ei=0;
  SegmentTree<int, int> seg(f,g,g,ti,ei);

  const int sz = 1<<20;
  seg.build(vector<int>(sz,0));

  for(int i=0;i<n;i++) seg.update(sz-as[i],sz,+1);
  for(int i=0;i<m;i++) seg.update(sz-bs[i],sz,-1);

  int q;
  cin>>q;
  auto check=[](int d){return d>0;};
  for(int i=0;i<q;i++){
    int t,k,v;
    cin>>t>>k>>v;
    k--;
    if(t==1){
      seg.update(sz-as[k],sz,-1);
      as[k]=v;
      seg.update(sz-as[k],sz,+1);
    }
    if(t==2){
      seg.update(sz-bs[k],sz,+1);
      bs[k]=v;
      seg.update(sz-bs[k],sz,-1);
    }
    int pos=seg.find(0,check);
    cout<<(pos<0?pos:sz-pos)<<"\n";
  }
  cout<<flush;
  return 0;
}
/*
  verified on 2019/10/28
  https://codeforces.com/contest/1179/problem/C
*/

signed main(){
  CFR569_C();
  return 0;
}
#endif

#undef call_from_test

signed main(){
  int n;
  cin>>n;
  EulerTourForBFS G(n);
  for(int i=1;i<n;i++){
    int u,v;
    cin>>u>>v;
    G.add_edge(u,v);
  }
  G.build();

  vector<int> as(n);
  for(int i=0;i<n;i++) cin>>as[i];

  using ll = long long;
  auto f=[&](ll a,ll b){return a+b;};
  auto g=[&](ll a,ll b){return a*b;};
  SegmentTree<ll, ll> seg(f,g,g,0,1);

  vector<ll> vs(n);
  for(int i=0;i<n;i++)
    vs[G.idx(i)]=as[i];
  seg.build(vs);

  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int x;
    cin>>x;

    ll sum=0;
    auto apply=
      [&](int l,int r){
        sum+=seg.query(l,r);
        seg.update(l,r,0);
      };

    int p=G.par[0][x];
    if(~p){
      int pp=G.par[0][p];
      if(~pp) G.exec(pp,0,apply);

      G.exec(p,0,apply);
      G.exec(p,1,apply);
    }

    G.exec(x,0,apply);
    G.exec(x,1,apply);
    G.exec(x,2,apply);

    seg.set_val(G.idx(x),sum);
    cout<<sum<<"\n";
  }

  return 0;
}
#endif