結果

問題 No.1216 灯籠流し/Lanterns
コンテスト
ユーザー beet
提出日時 2020-09-01 22:41:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,293 ms / 4,500 ms
コード長 8,903 bytes
コンパイル時間 3,767 ms
コンパイル使用メモリ 246,516 KB
最終ジャッジ日時 2025-01-14 03:18:39
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/4852"

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

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
/*
 * @docs docs/binaryindexedtree.md
 */
//BEGIN CUT HERE
template<typename T>
struct BIT{
  int n;
  vector<T> bit;
  // 1-indexed
  BIT(int n_):n(n_+1),bit(n+1,0){}

  T sum(int i){
    T s(0);
    for(int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }

  void add(int i,T a){
    if(i==0) return;
    for(int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }

  // [l, r)
  T query(int l,int r){
    return sum(r-1)-sum(l-1);
  }

  int lower_bound(int w){
    if(w<=0) return 0;
    int x=0,r=1;
    while(r<n) r<<=1;
    for(int k=r;k>0;k>>=1){
      if(x+k<=n&&bit[x+k]<w){
        w-=bit[x+k];
        x+=k;
      }
    }
    return x+1;
  }

  // 0-indexed
  T sum0(int i){return sum(i+1);}
  void add0(int i,T a){add(i+1,a);}
  T query0(int l,int r){return sum(r)-sum(l);}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif


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

//BEGIN CUT HERE
template<typename TV, const int N> void read_tuple_impl(TV&) {}
template<typename TV, const int N, typename Head, typename... Tail>
void read_tuple_impl(TV& ts) {
  get<N>(ts).emplace_back(*(istream_iterator<Head>(cin)));
  read_tuple_impl<TV, N+1, Tail...>(ts);
}
template<typename... Ts> decltype(auto) read_tuple(size_t n) {
  tuple<vector<Ts>...> ts;
  for(size_t i=0;i<n;i++) read_tuple_impl<decltype(ts), 0, Ts...>(ts);
  return ts;
}
//END CUT HERE

#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename F>
struct FixPoint : F{
  FixPoint(F&& f):F(forward<F>(f)){}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const{
    return F::operator()(*this,forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f){
  return FixPoint<F>{forward<F>(f)};
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
class EulerTourForVertex{
private:
  vector<int> ls,rs;
  int pos;

  void dfs(int v,int p){
    ls[v]=pos++;
    for(int u:G[v])
      if(u!=p) dfs(u,v);
    rs[v]=pos;
  }

public:
  vector< vector<int> > G;

  EulerTourForVertex(){}
  EulerTourForVertex(int n):ls(n),rs(n),G(n){}

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

  void build(int r=0){
    pos=0;
    dfs(r,-1);
  }

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

  template<typename F>
  void exec(int v,F f){
    f(ls[v],rs[v]);
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct LowestCommonAncestor{
  int n,h;
  vector< vector<int> > G,par;
  vector<int> dep;
  LowestCommonAncestor(){}
  LowestCommonAncestor(int n):n(n),G(n),dep(n){
    h=1;
    while((1<<h)<=n) h++;
    par.assign(h,vector<int>(n,-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){
    par[0][v]=p;
    dep[v]=d;
    for(int u:G[v])
      if(u!=p) dfs(u,v,d+1);
  }

  void build(int r=0){
    dfs(r,-1,0);
    for(int k=0;k+1<h;k++)
      for(int v=0;v<n;v++)
        if(~par[k][v])
          par[k+1][v]=par[k][par[k][v]];
  }

  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 distance(int u,int v){
    return dep[u]+dep[v]-dep[lca(u,v)]*2;
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

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

#define call_from_test
#include "eulertourforvertex.cpp"
#include "lowestcommonancestor.cpp"
#undef call_from_test

#endif
/**
 * @see https://smijake3.hatenablog.com/entry/2019/09/15/200200
 */
//BEGIN CUT HERE
struct AuxiliaryTree : EulerTourForVertex{
  using super = EulerTourForVertex;
  LowestCommonAncestor lca;

  vector<vector<int>> T;
  AuxiliaryTree(){}
  AuxiliaryTree(int n):super(n),lca(n),T(n){}

  void build(int r=0){
    super::build(r);
    lca.G=super::G;
    lca.build(r);
  }

  void add_aux_edge(int u,int v){
    T[u].emplace_back(v);
    T[v].emplace_back(u);
  }

  using super::idx;
  void query(vector<int> &vs){
    assert(!vs.empty());
    sort(vs.begin(),vs.end(),
         [&](int a,int b){return idx(a)<idx(b);});
    vs.erase(unique(vs.begin(),vs.end()),vs.end());

    int k=vs.size();
    stack<int> st;
    st.emplace(vs[0]);
    for(int i=0;i+1<k;i++){
      int w=lca.lca(vs[i],vs[i+1]);
      if(w!=vs[i]){
        int l=st.top();st.pop();
        while(!st.empty()&&lca.dep[w]<lca.dep[st.top()]){
          add_aux_edge(st.top(),l);
          l=st.top();st.pop();
        }
        if(st.empty()||st.top()!=w){
          st.emplace(w);
          vs.emplace_back(w);
        }
        add_aux_edge(w,l);
      }
      st.emplace(vs[i+1]);
    }

    while(st.size()>1){
      int c=st.top();st.pop();
      add_aux_edge(st.top(),c);
    }
  }

  void clear(const vector<int> &ws){
    for(int w:ws) T[w].clear();
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif


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

//BEGIN CUT HERE
template<typename V>
V compress(V vs){
  sort(vs.begin(),vs.end());
  vs.erase(unique(vs.begin(),vs.end()),vs.end());
  return vs;
}
template<typename T>
map<T, int> dict(const vector<T> &vs){
  map<T, int> res;
  for(int i=0;i<(int)vs.size();i++)
    res[vs[i]]=i;
  return res;
}
map<char, int> dict(const string &s){
  return dict(vector<char>(s.begin(),s.end()));
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  const char newl = '\n';
  using ll = long long;
  using P = pair<int, ll>;

  int n,q;
  cin>>n>>q;
  vector<vector<P>> G(n+1);
  AuxiliaryTree H(n+1);
  for(int i=1;i<n;i++){
    int a,b;
    ll c;
    cin>>a>>b>>c;
    G[a].emplace_back(b,c);
    G[b].emplace_back(a,c);
    H.add_edge(a,b);
  }
  // add 0 for root
  H.add_edge(0,1);
  H.build(0);

  const ll INF = 1e15;
  G[0].emplace_back(1,INF);

  vector<ll> dep(n+1);
  MFP([&](auto dfs,int v,int p,ll d)->void{
    dep[v]=d;
    for(auto [u,c]:G[v])
      if(u!=p) dfs(u,v,d+c);
  })(0,-1,0);

  auto [type,vs,ts,ls]=read_tuple<int, int, ll, ll>(q);

  // vanish vertices
  vector<int> rs(q);
  for(int i=0;i<q;i++){
    if(type[i]!=0) continue;
    int r=vs[i];
    ll d=dep[vs[i]]-ls[i];
    for(int k=H.lca.h-1;k>=0;k--){
      int p=H.lca.par[k][r];
      if(~p and d<=dep[p]) r=p;
    }
    rs[i]=H.lca.par[0][r];
  }

  vector<ll> pos;
  for(int i=0;i<q;i++)
    pos.emplace_back(ts[i]+dep[vs[i]]);
  pos=compress(pos);

  BIT<int> bit(pos.size());
  vector<int> cs(q);
  for(int i=0;i<q;i++)
    cs[i]=lower_bound(pos.begin(),pos.end(),ts[i]+dep[vs[i]])-pos.begin();

  queue<P> que;
  que.emplace(0,q);

  vector<int> ans(q);
  vector<vector<int>> add(n+1),sub(n+1),query(n+1);
  while(!que.empty()){
    auto [L,R]=que.front();que.pop();
    if(L+1==R) continue;
    int M=(L+R)>>1;

    vector<int> ss;
    for(int i=L;i<M;i++){
      if(type[i]==0){
        ss.emplace_back(vs[i]);
        ss.emplace_back(rs[i]);
      }
    }

    for(int i=M;i<R;i++)
      if(type[i]==1) ss.emplace_back(vs[i]);

    if(ss.empty()){
      que.emplace(L,M);
      que.emplace(M,R);
      continue;
    }

    ss.emplace_back(0);
    H.query(ss);

    for(int i=L;i<M;i++){
      if(type[i]==0){
        add[vs[i]].emplace_back(i);
        sub[rs[i]].emplace_back(i);
      }
    }

    for(int i=M;i<R;i++)
      if(type[i]==1) query[vs[i]].emplace_back(i);

    auto expand=[&](int v){
      for(int i:add[v]) bit.add0(cs[i],+1);
      for(int i:sub[v]) bit.add0(cs[i],-1);
    };

    MFP([&](auto dfs,int v,int p)->void{
      for(int i:query[v])
        ans[i]-=bit.sum0(cs[i]);

      for(int u:H.T[v])
        if(u!=p) dfs(u,v);
      expand(v);

      for(int i:query[v])
        ans[i]+=bit.sum0(cs[i]);
    })(0,-1);

    H.clear(ss);

    for(int i=L;i<M;i++){
      if(type[i]==0){
        add[vs[i]].clear();
        sub[rs[i]].clear();
      }
    }

    for(int i=M;i<R;i++)
      if(type[i]==1) query[vs[i]].clear();

    que.emplace(L,M);
    que.emplace(M,R);
  }

  for(int i=0;i<q;i++)
    if(type[i]==1) cout<<ans[i]<<newl;

  return 0;
}
0