結果
問題 | No.650 行列木クエリ |
ユーザー |
![]() |
提出日時 | 2018-02-09 22:56:10 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 4,788 bytes |
コンパイル時間 | 1,926 ms |
コンパイル使用メモリ | 187,108 KB |
実行使用メモリ | 25,492 KB |
最終ジャッジ日時 | 2024-10-09 08:56:00 |
合計ジャッジ時間 | 3,268 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;struct HLDecomposition {Int n,pos;vector<vector<Int> > G;vector<Int> vid, head, sub, hvy, par, dep, inv, type;HLDecomposition(){}HLDecomposition(Int sz):n(sz),pos(0),G(n),vid(n,-1),head(n),sub(n,1),hvy(n,-1),par(n),dep(n),inv(n),type(n){}void add_edge(Int u, Int v) {G[u].push_back(v);G[v].push_back(u);}void build(vector<Int> rs={0}) {Int c=0;for(Int r:rs){dfs(r);bfs(r, c++);}}void dfs(Int rt) {using T = pair<Int, Int>;stack<T> st;par[rt]=-1;dep[rt]=0;st.emplace(rt,0);while(!st.empty()){Int v=st.top().first;Int &i=st.top().second;if(i<(Int)G[v].size()){Int u=G[v][i++];if(u==par[v]) continue;par[u]=v;dep[u]=dep[v]+1;st.emplace(u,0);}else{st.pop();Int res=0;for(Int u:G[v]){if(u==par[v]) continue;sub[v]+=sub[u];if(res<sub[u]) res=sub[u],hvy[v]=u;}}}}void bfs(Int r,Int c) {Int &k=pos;queue<Int> q({r});while(!q.empty()){Int h=q.front();q.pop();for(Int i=h;i!=-1;i=hvy[i]) {type[i]=c;vid[i]=k++;inv[vid[i]]=i;head[i]=h;for(Int j:G[i])if(j!=par[i]&&j!=hvy[i]) q.push(j);}}}// for_each(vertex)// [l,r] <- attention!!void for_each(Int u, Int v, const function<void(Int, Int)>& f) {while(1){if(vid[u]>vid[v]) swap(u,v);f(max(vid[head[v]],vid[u]),vid[v]);if(head[u]!=head[v]) v=par[head[v]];else break;}}// for_each(edge)// [l,r] <- attention!!void for_each_edge(Int u, Int v, const function<void(Int, Int)>& f) {while(1){if(vid[u]>vid[v]) swap(u,v);if(head[u]!=head[v]){f(vid[head[v]],vid[v]);v=par[head[v]];} else{if(u!=v) f(vid[u]+1,vid[v]);break;}}}Int lca(Int u,Int v){while(1){if(vid[u]>vid[v]) swap(u,v);if(head[u]==head[v]) return u;v=par[head[v]];}}Int distance(Int u,Int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}};template <typename T,typename E>struct SegmentTree{typedef function<T(T,T)> F;typedef function<T(T,E)> G;Int n;F f;G g;T d1;E d0;vector<T> dat;SegmentTree(){};SegmentTree(Int n_,F f,G g,T d1,vector<T> v=vector<T>()):f(f),g(g),d1(d1){init(n_);if(n_==(Int)v.size()) build(n_,v);}void init(Int n_){n=1;while(n<n_) n*=2;dat.clear();dat.resize(2*n-1,d1);}void build(Int n_, vector<T> v){for(Int i=0;i<n_;i++) dat[i+n-1]=v[i];for(Int i=n-2;i>=0;i--)dat[i]=f(dat[i*2+1],dat[i*2+2]);}void update(Int k,E a){k+=n-1;dat[k]=g(dat[k],a);while(k>0){k=(k-1)/2;dat[k]=f(dat[k*2+1],dat[k*2+2]);}}inline T query(Int a,Int b){T vl=d1,vr=d1;for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {if(l&1) vl=f(vl,dat[(l++)-1]);if(r&1) vr=f(dat[(--r)-1],vr);}return f(vl,vr);}Int find(Int a,Int b,function<bool(T)> &check,Int k,Int l,Int r){if(!check(dat[k])||r<=a||b<=l) return -1;if(k>=n-1) return k-(n-1);Int m=(l+r)>>1;Int vl=find(a,b,check,k*2+1,l,m);if(~vl) return vl;return find(a,b,check,k*2+2,m,r);}Int find(Int a,Int b,function<bool(T)> &check){return find(a,b,check,0,0,n);}};struct FastIO{FastIO(){cin.tie(0);ios::sync_with_stdio(0);}}fastio_beet;//INSERT ABOVE HEREstruct M{Int a,b,c,d;M():a(1),b(0),c(0),d(1){}M(Int a,Int b,Int c,Int d):a(a),b(b),c(c),d(d){}//M(const M &v):a(v.a),b(v.b),c(v.c),d(v.d){}}E;signed main(){Int n;cin>>n;HLDecomposition hld(n);vector<int> X,Y;for(Int i=1;i<n;i++){Int a,b;cin>>a>>b;X.emplace_back(a);Y.emplace_back(b);hld.add_edge(a,b);}hld.build();const Int MOD = 1e9+7;SegmentTree<M,M>::F f=[MOD](M x,M y){M r(0,0,0,0);r.a=x.a*y.a+x.b*y.c;r.b=x.a*y.b+x.b*y.d;r.c=x.c*y.a+x.d*y.c;r.d=x.c*y.b+x.d*y.d;r.a%=MOD;r.b%=MOD;r.c%=MOD;r.d%=MOD;return r;};SegmentTree<M,M>::G g=[](M x,M y){return y;};SegmentTree<M,M> seg(n,f,g,E);Int q;cin>>q;for(Int i=0;i<q;i++){char c;cin>>c;if(c=='x'){Int v,a,b,c,d;cin>>v>>a>>b>>c>>d;int z=(hld.dep[X[v]]>hld.dep[Y[v]]?X[v]:Y[v]);seg.update(hld.vid[z],M(a,b,c,d));//cout<<z<<":"<<hld.vid[z]<<endl;}if(c=='g'){Int x,y;cin>>x>>y;M ans=E;hld.for_each_edge(x,y,[&](Int l,Int r){ans=f(seg.query(l,r+1),ans);//cout<<l<<" "<<r<<endl;});cout<<ans.a<<" "<<ans.b<<" "<<ans.c<<" "<<ans.d<<endl;}}return 0;}