This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../tree/eulertourforedge.cpp" #include "../../datastructure/binaryindexedtree.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n; cin>>n; EulerTourForEdge et(n); for(int i=0;i<n;i++){ int k; cin>>k; for(int j=0;j<k;j++){ int c; cin>>c; et.add_edge(i,c); } } et.build(); BIT<int> bit(2*n); int q; cin>>q; for(int i=0;i<q;i++){ int t; cin>>t; if(t==0){ int v,w; cin>>v>>w; auto g=[&](int k,int d){bit.add(k,d);}; et.update(v,w,g); } if(t==1){ int u; cin>>u; int res=0; et.query(0,u,[&](int l,int r){res+=bit.query(l,r);}); cout<<res<<"\n"; } } return 0; }
#line 1 "test/aoj/GRL_5_D.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "tree/eulertourforedge.cpp" #line 3 "tree/eulertourforedge.cpp" using namespace std; #endif //BEGIN CUT HERE class EulerTourForEdge{ private: vector<int> ds,us,dep,btm; void dfs(int v,int p,int d){ dep[v]=d; for(int u:G[v]){ if(u==p) continue; ds[u]=btm.size(); btm.emplace_back(u); dfs(u,v,d+1); us[u]=btm.size(); btm.emplace_back(u); } } public: vector< vector<int> > G; EulerTourForEdge(int n): ds(n),us(n),dep(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){ btm.clear(); ds[r]=btm.size(); btm.emplace_back(r); dfs(r,-1,0); us[r]=btm.size(); btm.emplace_back(r); } int child(int u,int v){ return dep[u]<dep[v]?v:u; } int bottom(int e){ return btm[e]; } // lca(u, v) must be u or v template<typename F> void query(int u,int v,F f){ if(dep[u]>dep[v]) swap(u,v); f(ds[u]+1,ds[v]+1); } template<typename T,typename G> void update(int v,T x,G g){ g(ds[v], x); g(us[v],-x); } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "datastructure/binaryindexedtree.cpp" #line 3 "datastructure/binaryindexedtree.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T> class BIT{ private: // \sum_{j < i} v[j] T sum(int i){ T s(0); for(int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } public: int n; vector<T> bit; BIT(int n_):n(n_+1),bit(n_+2,0){} // v[i] += a void add(int i,T a){ for(int x=++i;x<=n;x+=(x&-x)) bit[x]+=a; } // \sum_{l <= i < r} v[i] T query(int l,int r){return sum(r)-sum(l);} // min({x | sum(x) >= w}) int lower_bound(const T w){ if(w<=0) return 0; T r=w; int x=0,p=1; while(p<n) p<<=1; for(int k=p;k>0;k>>=1){ if(x+k<=n and bit[x+k]<r){ r-=bit[x+k]; x+=k; } } x++; assert(sum(x-1)<w and sum(x)>=w); return x; } // min({x | sum(x) > w}) int upper_bound(T w){return lower_bound(w+1);} }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 9 "test/aoj/GRL_5_D.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n; cin>>n; EulerTourForEdge et(n); for(int i=0;i<n;i++){ int k; cin>>k; for(int j=0;j<k;j++){ int c; cin>>c; et.add_edge(i,c); } } et.build(); BIT<int> bit(2*n); int q; cin>>q; for(int i=0;i<q;i++){ int t; cin>>t; if(t==0){ int v,w; cin>>v>>w; auto g=[&](int k,int d){bit.add(k,d);}; et.update(v,w,g); } if(t==1){ int u; cin>>u; int res=0; et.query(0,u,[&](int l,int r){res+=bit.query(l,r);}); cout<<res<<"\n"; } } return 0; }