結果

問題 No.650 行列木クエリ
コンテスト
ユーザー ふぃぼん
提出日時 2026-10-03 16:37:15
言語 C++23(gnu拡張)
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 415 ms / 2,000 ms
+ 0µs
コード長 4,479 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,813 ms
コンパイル使用メモリ 403,632 KB
実行使用メモリ 115,956 KB
最終ジャッジ日時 2026-10-03 16:37:37
合計ジャッジ時間 9,398 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#if __has_include(<acl_bits.hpp>)
#include <acl_bits.hpp>
#else
#include <bits/stdc++.h>
#include <atcoder/all>
#endif
using namespace atcoder;
using namespace std;
using ll=long long;
using ld=long double;
using P = pair<ll,ll>;
using TUP = tuple<ll,ll,ll>;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define drep(i,n) for (int i = (n-1); i >= 0; --i)
template<typename t,typename u>inline bool chmax(t&a,u b){return a<b?a=b,1:0;}
template<typename t,typename u>inline bool chmin(t&a,u b){return a>b?a=b,1:0;}
inline int yn(bool b){cout<<(b?"Yes\n":"No\n");return 0;}
const vector<int> di={1,0,-1,0},dj={0,1,0,-1};
using mint = modint1000000007;
inline ostream&operator<<(ostream&os,const mint& x){os<<x.val();return os;};
template <typename t>ostream&operator<<(ostream&os,const vector<t>&x){for(t i:x)os<<i<<' ';return os;}
template <typename t>ostream&operator<<(ostream&os,const vector<vector<t>>&x){for(const vector<t>&i:x)os<<i<<'\n';return os;}
const ll inf=2e18;

struct hld{
	int n;
	vector<int> vertex,id,head,par,dep;
	hld(vector<vector<int>> g){
		n=g.size();
		id.resize(n);
		head.resize(n);
		par.resize(n);
		dep.resize(n);
		{
			auto f=[&](auto f,int x,int px)->int{
				int cnt=1,mx=0;
				rep(i,g[x].size()){
					int nx=g[x][i];
					if(nx==px)continue;
					int s=f(f,nx,x);
					cnt+=s;
					if(chmax(mx,s))swap(g[x][0],g[x][i]);
				}
				return cnt;
			};
			f(f,0,0);
		}
		{
			auto f=[&](auto f,int x,int px)->void{
				id[x]=vertex.size();
				vertex.push_back(x);
				for(int nx:g[x])if(px!=nx){
					par[nx]=x;
					dep[nx]=dep[x]+1;
					head[nx]=(nx==g[x][0]?head[x]:nx);
					f(f,nx,x);
				}
			};
			f(f,0,0);
		}
	}
	int lca(int u,int v){
		while(head[u]!=head[v]){
			if(id[u]>id[v])u=par[head[u]];
			else v=par[head[v]];
		}
		return id[u]<id[v]?u:v;
	}
	int dist(int u,int v){
		int c=lca(u,v);
		return dep[u]+dep[v]-2*dep[c];
	}
	int level_ancestor(int u,int d){
		if(dep[u]<d)return -1;
		while(dep[head[u]]>d){
			u=par[head[u]];
		}
		return vertex[id[u]-(dep[u]-d)];
	}
	int jump_up(int u,int steps){
		return level_ancestor(u,dep[u]-steps);
	}
	int jump(int u,int v,int steps){
		int c=lca(u,v);
		int uc=dep[u]-dep[c];
		int vc=dep[v]-dep[c];
		if(steps < uc)return jump_up(u,steps);
		else if(steps-uc<=vc)return jump_up(v,uc+vc-steps);
		else return -1;
	}
	template<typename F,typename G>
	void foreach(int u,int v,const F& f_uc,const G& f_vc){
		stack<pair<int,int>> st;
		while(head[u]!=head[v]){
			if(id[u]>id[v]){
				f_uc(id[head[u]],id[u]+1);
				u=par[head[u]];
			}else{
				f_vc(id[head[v]],id[v]+1);
				v=par[head[v]];
			}
		}
		if(id[u]<id[v])f_vc(id[u],id[v]+1);
		else f_uc(id[v],id[u]+1);
	}
	template<typename F,typename G>
	void foreach_edge(int u,int v,const F& f_uc,const G& f_vc){
		stack<pair<int,int>> st;
		while(head[u]!=head[v]){
			if(id[u]>id[v]){
				f_uc(id[head[u]],id[u]+1);
				u=par[head[u]];
			}else{
				f_vc(id[head[v]],id[v]+1);
				v=par[head[v]];
			}
		}
		if(id[u]<id[v])f_vc(id[u]+1,id[v]+1);
		else f_uc(id[v]+1,id[u]+1);
	}
	template<typename F>
	void foreach(int u,int v,const F& f){
		foreach(u,v,f,f);
	}
	template<typename F>
	void foreach_edge(int u,int v,const F& f){
		foreach_edge(u,v,f,f);
	}
};

template<typename T> vector<vector<T>> mat_mul(const vector<vector<T>>& a,const vector<vector<T>>& b){
    if(a[0].size()!=b.size())return vector(a.size(),vector<T>(b[0].size()));
    vector res(a.size(),vector<T>(b[0].size()));
    rep(i,a.size())rep(j,b[0].size())rep(k,b.size()){
        res[i][j]+=a[i][k]*b[k][j];
    }
    return res;
}

using S=vector<vector<mint>>;
S op1(S a,S b){return mat_mul(a,b);}
S op2(S a,S b){return mat_mul(b,a);}
S e(){return {{1,0},{0,1}};}

int main(){
	int n;
	cin>>n;
	vector<vector<int>> g(n);
	vector<P> es;
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
		es.emplace_back(u,v);
	}
	hld hl(g);
	segtree<S,op1,e> seg1(n);
	segtree<S,op2,e> seg2(n);

	int q;
	cin>>q;
	rep(qi,q){
		char t;
		cin>>t;
		if(t=='x'){
			int i;
			cin>>i;
			vector x(2,vector<mint>(2));
			rep(ii,2)rep(j,2){
				int tmp;
				cin>>tmp;
				x[ii][j]=tmp;
			}
			auto[u,v]=es[i];
			int c=hl.id[u==hl.lca(u,v)?v:u];
			seg1.set(c,x);
			seg2.set(c,x);
		}else{
			int i,j;
			cin>>i>>j;
			S ls=e(),rs=e();
			hl.foreach_edge(i,j,[&](int l,int r){
					ls=mat_mul(ls,seg2.prod(l,r));
					},[&](int l,int r){
					rs=mat_mul(seg1.prod(l,r),rs);
					});
			S ans=mat_mul(ls,rs);
			cout<<ans[0]<<ans[1]<<endl;
		}
	}
}
0