結果
| 問題 |
No.650 行列木クエリ
|
| コンテスト | |
| ユーザー |
 walkre
|
| 提出日時 | 2018-02-10 00:12:56 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 12,050 bytes |
| コンパイル時間 | 3,514 ms |
| コンパイル使用メモリ | 225,408 KB |
| 実行使用メモリ | 84,112 KB |
| 最終ジャッジ日時 | 2024-10-09 08:21:55 |
| 合計ジャッジ時間 | 6,398 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 6 WA * 4 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using i64=int64_t;
#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
os << "[";
for (const auto &v : vec) {
os << v << ",";
}
os << "]";
return os;
}
template<class segment_type,class connection_type> struct HeavyLightDecomposer{
const vector<vector<int>> graph;
const int root,n;
vector<int> parent,subtree_size,depth,
first,last,prev,next,path_id,local_index;
vector<vector<int>> paths,children;
vector<segment_type> segments; //pathに乗っけるデータ構造用
vector<connection_type> connections; //pathとpathを接続する辺に対応する
HeavyLightDecomposer(const vector<vector<int>> &graph,int root):graph(graph),root(root),n(graph.size()),
parent(n),subtree_size(n,1),depth(n),first(n),last(n),prev(n,-1),next(n,-1),path_id(n),local_index(n)
{
preprocess();
decompose();
segments.resize(paths.size());
connections.resize(paths.size());
}
void preprocess(){
stack<tuple<int,int,int>> dfs_stack;
dfs_stack.push(make_tuple(root,-1,0));
while(!dfs_stack.empty()){
auto t=dfs_stack.top();
dfs_stack.pop();
int v=get<0>(t),p=get<1>(t),i=get<2>(t);
if(i==0){
if(v!=root) depth[v]=depth[p]+1;
dfs_stack.push(make_tuple(v,p,1));
for(int u:graph[v]){
if(u==p) continue;
dfs_stack.push(make_tuple(u,v,0));
}
}else{
parent[v]=p;
for(int u:graph[v]){
if(u==p) continue;
subtree_size[v]+=subtree_size[u];
}
}
}
}
using pii=pair<int,int>;
void decompose(){
int cnt=0;
stack<pii> dfs_stack;
dfs_stack.push(make_pair(root,0));
while(!dfs_stack.empty()){
auto p=dfs_stack.top();
dfs_stack.pop();
int v=p.first,id=p.second;
if(paths.size()<=cnt) paths.resize(cnt+1);
if(children.size()<=cnt) children.resize(cnt+1);
int cur=v;
while(cur!=-1){
paths[id].push_back(cur);
int heavy_edge=-1;
for(int u:graph[cur]){
if(u==parent[cur]) continue;
if(heavy_edge==-1 and subtree_size[u]*2>=subtree_size[cur]-1) heavy_edge=u;
else{
++cnt;
children[id].push_back(cnt);
dfs_stack.push(make_pair(u,cnt));
}
}
cur=heavy_edge;
}
for(int i=0; i<paths[id].size(); ++i){
int u=paths[id][i];
first[u]=paths[id].front();
last[u]=paths[id].back();
if(i!=0) prev[u]=paths[id][i-1];
if(i!=paths[id].size()-1) next[u]=paths[id][i+1];
path_id[u]=id;
local_index[u]=i;
}
}
}
int size()const{
return n;
}
int go_up(int v){ //vが含まれるpathの先頭のノードの親のglobal_indexを返す
return parent[first[v]];
}
int lca(int u,int v){
while(path_id[u]!=path_id[v]){
if(depth[first[u]]<depth[first[v]]) v=go_up(v);
else u=go_up(u);
}
return depth[u]<depth[v]?u:v;
}
//O(log_2(n))
int highest_child(int path_id,int idx){ //local indexがidx以下のノードに接続されている子パスの中で最も上にあるもののchildren[path_id]中でのindex
int lb=-1,ub=children[path_id].size();
while(ub-lb>1){
int m=(lb+ub)/2;
if(local_index[go_up(paths[children[path_id][m]].front())]>=idx) ub=m;
else lb=m;
}
return ub;
};
};
template<class T,T op(T,T)> class segtree{
public:
int n,size_;
vector<T> dat;
T id_;
segtree()=default;
segtree(int size,T id,T initial_value){ init(size,id,initial_value); }
void init(int size,T id,T initial_value){
size_=size;
id_=id;
n=1;
while(n<size) n*=2;
dat.assign(2*n-1,id);
for(int i=0; i<size; ++i) update(i,initial_value);
}
int size()const{ return size_; }
void update(int k, T a) {
k+=n-1; // leaf
dat[k]=a;
while(k>0) {
k=(k-1)/2;
dat[k]=op(dat[k*2+1],dat[k*2+2]);
}
}
T at(int index){ return dat[index+n-1]; }
void add(int k,T a){ update(k,at(k)+a); }
T query(int a,int b) { return query(a,b,0,0,n); }
T query(int a,int b,int k,int l,int r) {
if(r<=a or b<=l) return id_;
if(a<=l and r<=b) return dat[k];
int m=(l+r)/2;
return op(query(a,b,k*2+1,l,m),query(a,b,k*2+2,m,r));
}
};
template<i64 p> class Fp{
public:
i64 x;
Fp():x(0){}
Fp(i64 x_):x((x_%p+p)%p){}
Fp operator+()const{ return Fp(x); }
Fp operator-()const{ return Fp(-x); }
Fp& operator+=(const Fp& y){ x=((x+y.x)%p+p)%p; return *this ;}
Fp& operator-=(const Fp& y){ return *this+=-y; }
Fp& operator*=(const Fp& y){ x=x*y.x%p; return *this; }
Fp& operator/=(const Fp& y){ return *this*=Fp(inverse(y.x)); }
Fp operator+(const Fp& y)const{ return Fp(x)+=y; }
Fp operator-(const Fp& y)const{ return Fp(x)-=y; }
Fp operator*(const Fp& y)const{ return Fp(x)*=y; }
Fp operator/(const Fp& y)const{ return Fp(x)/=y; }
bool operator==(const Fp& y)const{ return x==y.x; }
bool operator!=(const Fp& y)const{ return !(*this==y); }
i64 extgcd(i64 a,i64 b,i64 &x,i64 &y){
i64 d=a;
if(b!=0){
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
} else {
x=1; y=0;
}
return d;
}
i64 inverse(i64 a){
i64 x,y;
extgcd(a,p,x,y);
return (x%p+p)%p;
}
};
template<i64 p> ostream &operator<<(ostream& os, const Fp<p> &x) { os << x.x; return os; }
template<i64 p> i64 abs(const Fp<p>& x){ return x.x; }
template<class K> class matrix{
public:
int m,n;
vector<vector<K>> a;
matrix(){
m=n=2;
a=vector<vector<K>>(2,vector<K>(2));
a[0][0]=a[1][1]=1;
}
matrix(int m_,int n_):m(m_),n(n_),a(m_,vector<K>(n_)){}
matrix(const vector<vector<K>> &v):m(v.size()),n((v.size()==0 or v[0].size()==0)?0:v[0].size()),a(v){}
//matrix(const matrix<K>& other)=default;
//~matrix()=default;
vector<K>& operator[](int i){ assert(0<=i); assert(i<m); return a[i]; }
matrix<K> operator+()const{ return *this; }
matrix<K> operator-()const{ return K(-1)**this; }
K at(int i,int j)const{ return a[i][j]; }
matrix<K>& operator=(const matrix<K> &other)=default;
matrix<K>& operator+=(const matrix<K> &other){ assert(m==other.m); assert(n==other.n); for(int i=0; i<m; ++i) for(int j=0; j<n; ++j) (*this)[i][j]+=other[i][j]; return *this; }
matrix<K>& operator-=(const matrix<K> &other){ return (*this)+=-other; }
matrix<K>& operator*=(const matrix<K> &other){
assert(n==other.m);
vector<vector<K>> b(m,vector<K>(other.n));
for(int i=0; i<m; ++i) for(int j=0; j<other.n; ++j) for(int k=0; k<n; ++k) b[i][j]+=(*this)[i][k]*other.at(k,j);
a=b;
return *this;
}
matrix<K>& operator/=(const K& k){ assert(k!=K(0)); for(int i=0; i<m; ++i) for(int j=0; j<n; ++j) (*this)[i][j]/=k; return *this; }
matrix<K>& operator%=(const K& k){ assert(k!=K(0)); for(int i=0; k<m; ++i) for(int j=0; j<n; ++j) (*this)[i][j]=((*this)[i][j]+k)%k; return *this; }
matrix<K> operator+(const matrix<K>& other)const{ return matrix<K>(*this)+=other; }
matrix<K> operator-(const matrix<K>& other)const{ return matrix<K>(*this)-=other; }
matrix<K> operator*(const matrix<K>& other)const{ return matrix<K>(*this)*=other; }
matrix<K> operator/(const K& k)const{ return matrix(*this)/=k; }
matrix<K> operator%(const K& k)const{ return matrix(*this)%=k; }
bool operator==(const matrix<K> &other)const{
if(m!=other.m or n!=other.n) return false;
for(int i=0; i<m; ++i) for(int j=0; j<n; ++j) if((*this)[i][j]!=other[i][j]) return false;
return true;
}
bool operator!=(const matrix<K> &other)const{ return !((*this)==other); }
static matrix<K> E(int m){
assert(0<=m);
matrix<K> E_(m,m);
for(int i=0; i<m; ++i) E_[i][i]=K(1);
return E_;
}
static matrix<K> e(int m,int i){
assert(0<=i);
assert(i<m);
matrix<K> e_;
e_[i][0]=K(1);
return e_;
}
};
template<class K> matrix<K> operator*(const K& k,const matrix<K> &x){
matrix<K> res(x);
for(int i=0; i<x.m; ++i) for(int j=0; j<x.n; ++j) res[i][j]*=k;
return res;
}
template<class K> K tr(const matrix<K>& x){
assert(x.m==x.n);
K res(0);
for(int i=0; i<x.m; ++i) res+=x.at(i,i);
return res;
}
const i64 mod=1000000007;
using mat=matrix<Fp<mod>>;
mat mul(mat a,mat b){
mat res(2,2);
rep(i,0,2) rep(j,0,2) rep(k,0,2) res[i][j]+=a[i][k]*b[k][j];
return res;
}
void solve(){
int n;
cin >> n;
vector<vector<int>> tree(n);
vector<pair<int,int>> edges;
rep(i,0,n-1){
int a,b;
cin >> a >> b;
tree[a].push_back(b);
tree[b].push_back(a);
edges.push_back(make_pair(a,b));
}
vector<int> par(n),dep(n);
function<void(int,int,int)> dfs=[&](int u,int p,int d){
par[u]=p;
dep[u]=d;
for(int v:tree[u]){
if(v==p) continue;
dfs(v,u,d+1);
}
};
dfs(0,-1,0);
rep(i,0,n-1) if(dep[edges[i].first]>dep[edges[i].second]) swap(dep[edges[i].first],dep[edges[i].second]);
using seg_mat=segtree<mat,mul>;
HeavyLightDecomposer<seg_mat,vector<seg_mat>> hld(tree,0);
vector<mat> connections(n,mat::E(2));
rep(i,0,hld.segments.size()){
hld.segments[i].init(hld.paths[i].size()-1, mat::E(2), mat::E(2));
}
int q;
cin >> q;
rep(i,0,q){
char t;
cin >> t;
if(t=='x'){
int i;
i64 x00,x01,x10,x11;
cin >> i >> x00 >> x01 >> x10 >> x11;
int a=edges[i].first,b=edges[i].second;
mat tmp(2,2);
tmp[0][0]=x00;
tmp[0][1]=x01;
tmp[1][0]=x10;
tmp[1][1]=x11;
if(hld.path_id[a]==hld.path_id[b]){
hld.segments[hld.path_id[a]].update(min(hld.local_index[a],hld.local_index[b]),tmp);
}else{
connections[hld.local_index[a]<hld.local_index[b]?a:b]=tmp;
}
}else{
int i,j;
cin >> i >> j;
mat ans;
while(true){
int pathj=hld.path_id[j];
if(hld.path_id[i]==hld.path_id[j]){
int l=hld.local_index[i],r=hld.local_index[j];
print(l);
print(r);
ans=hld.segments[pathj].query(l,r)*ans;
break;
}
ans=hld.segments[pathj].query(0,hld.local_index[j])*ans;
ans=connections[hld.first[j]]*ans;
j=hld.go_up(j);
}
cout << ans[0][0] << " " << ans[0][1] << " " << ans[1][0] << " " << ans[1][1] << endl;
}
}
}
int main(){
std::cin.tie(0);
std::ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(16);
solve();
return 0;
}