結果

問題 No.1038 TreeAddQuery
ユーザー beetbeet
提出日時 2020-03-02 20:50:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,517 bytes
コンパイル時間 2,421 ms
コンパイル使用メモリ 215,908 KB
実行使用メモリ 20,032 KB
最終ジャッジ日時 2024-10-15 01:58:41
合計ジャッジ時間 9,215 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,528 KB
testcase_01 AC 4 ms
6,656 KB
testcase_02 AC 4 ms
6,528 KB
testcase_03 AC 111 ms
7,040 KB
testcase_04 AC 151 ms
6,912 KB
testcase_05 AC 78 ms
6,912 KB
testcase_06 AC 78 ms
6,784 KB
testcase_07 AC 146 ms
6,784 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;


const int MAX = 1e5 + 10;

int P[MAX*2]={};
int D[MAX*2]={};
int E[MAX*2]={};
int F[MAX*2]={};
int A[MAX*2]={};
int B[MAX*2]={};
int ht[MAX*2]={};

int dat[20][MAX / 5] = {};

struct LCA{
  const int lg = 12;
  const int sz = 1<<lg;
  const int ms = sz-1;
  int n;
  vector<int> T;
  vector<vector<int>> G;
  LCA(int n):
    n(n),T(sz,0),G(n){
    memset(P,-1,sizeof(P));
    memset(A,-1,sizeof(A));
    memset(dat,-1,sizeof(dat));
  }

  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 k=0,u;
    vector<int> iter(n,0);

    using T = tuple<int, int, int>;
    stack<T> st;

  START:
    F[v]=d;
    D[v]=k;
    A[k]=P[v]=p;
    E[k++]=d;
    for(;iter[v]<(int)G[v].size();iter[v]++){
      u=G[v][iter[v]];
      if(u==p) continue;
      st.emplace(v,p,d);
      p=v;v=u;d=d+1;
      goto START;
    END:
      tie(v,p,d)=st.top();st.pop();
    }

    A[k]=P[v];
    E[k++]=d-1;

    if(!st.empty()) goto END;
  }

  // if it need leftmost, then add: if(E[i]==E[j]) return i<j?i:j;
  inline int comp(int i,int j){return E[i]<E[j]?i:j;};
  inline int comp(int i,int j,int k){return comp(comp(i,j),k);};

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

    B[0]=1;
    for(int i=1;i<n*2;i++) B[i/lg]|=(E[i-1]<E[i])<<(i%lg);

    for(int b=0;b<sz;b++){
      int e=0,w=1,&x=T[b];
      for(int i=0;i<lg;i++){
        if((b>>i)&1) e++;
        else e--;
        if(e<w) e=w,x=i;
      }
    }

    int m=(n*2+lg-1)/lg;
    int h=1;
    while((1<<h)<m) h++;
    // dat.assign(h,vector<int>(m,-1));
    // ht.assign(m+1,0);
    for(int j=2;j<=m;j++) ht[j]=ht[j>>1]+1;

    for(int j=0;j<n*2;j++){
      if(dat[0][j/lg]<0) dat[0][j/lg]=j;
      dat[0][j/lg]=comp(dat[0][j/lg],j);
    }

    for(int i=1,p=1;i<h;i++,p<<=1)
      for(int j=0;j<m;j++)
        dat[i][j]=comp(dat[i-1][j],dat[i-1][min(j+p,m-1)]);
  }

  inline int cs(int a,int b){
    int l=b-a;
    return comp(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]);
  }

  inline int es(int i,int l,int r){
    int x=r-i*lg+1,y=l-i*lg;
    int b=(((B[i]|(ms<<x))>>y)|(ms<<(lg-y)))&ms;
    return l+T[b];
  }

  inline int ls(int i,int l){
    int k=l-i*lg;
    int b=((B[i]>>k)|(ms<<(lg-k)))&ms;
    return l+T[b];
  }

  inline int rs(int j,int r){
    int k=r-j*lg+1;
    int b=(B[j]|(ms<<k))&ms;
    return j*lg+T[b];
  }

  inline int rmq(int l,int r){
    int i=l/lg,j=r/lg;
    if(i==j) return es(i,l,r);
    if(i+1==j) return comp(ls(i,l),rs(j,r));
    return comp(ls(i,l),cs(i+1,j),rs(j,r));
  }

  int lca(int l,int r){
    if(l==r) return l;
    if(D[l]>D[r]) swap(l,r);
    int x=D[l],y=D[r];
    int m=rmq(x,y);
    return m==x?l:A[m];
  }

  inline int distance(int u,int v){
    return F[u]+F[v]-F[lca(u,v)]*2;
  }
};

//INSERT ABOVE HERE
int xs[MAX],ys[MAX],zs[MAX];
signed main(){
  int n,q;
  cin>>n>>q;
  LCA G(n);
  for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G.add_edge(a,b);
  }
  G.build(0);

  for(int i=0;i<q;i++) cin>>xs[i]>>ys[i]>>zs[i],xs[i]--;
  for(int i=0;i<q;i++){
    long long res=0;
    int v=xs[i];
    for(int j=0;j<i;j++)
      if(G.distance(v,xs[j])<=ys[j]) res+=zs[j];
    cout<<res<<"\n";
  }
  cout<<flush;
  return 0;
}
0