結果

問題 No.650 行列木クエリ
ユーザー beetbeet
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 HERE
struct 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0