結果

問題 No.650 行列木クエリ
ユーザー hashiryohashiryo
提出日時 2019-06-03 19:36:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 715 ms / 2,000 ms
コード長 5,499 bytes
コンパイル時間 2,761 ms
コンパイル使用メモリ 196,292 KB
実行使用メモリ 57,608 KB
最終ジャッジ日時 2024-09-17 20:34:19
合計ジャッジ時間 6,615 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll> Pll;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;

ll extgcd(ll a, ll b, ll &x, ll &y) {
    ll g = a; x = 1; y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

ll invMod(ll a, ll m) {
    ll x, y;
    if (extgcd(a, m, x, y) == 1) return (x + m) % m;
    else                         return 0; // unsolvable
}

template<int mod> struct Matrix {
    vector<vector<long long> > val;
    Matrix(int n, int m, long long x = 0) : val(n, vector<long long>(m, x)) {}
    void init(int n, int m, long long x = 0) {val.assign(n, vector<long long>(m, x));}
    size_t size() const {return val.size();}
    inline vector<long long>& operator [] (int i) {return val[i];}
    Matrix<mod>& operator=(const Matrix<mod> b){
      for(ll i=0;i<(ll)val.size();i++){
        for(ll j=0;j<(ll)val[i].size();j++){
          val[i][j]=b.val[i][j];
        }
      }
      return *this;
    }
};

// O( n )
template<int mod> Matrix<mod> identity(int n) {
    Matrix<mod> A(n, n);
    for (int i = 0; i < n; ++i) A[i][i] = 1;
    return A;
}

// O( n^3 )
template<int mod> Matrix<mod> mul(Matrix<mod> A, Matrix<mod> B) {
    Matrix<mod> C(A.size(), B[0].size());
    for (int i = 0; i < (ll)C.size(); ++i)
        for (int j = 0; j <(ll) C[i].size(); ++j)
            for (int k = 0; k < (ll)A[i].size(); ++k)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]%mod)%mod;
    return C;
}
// O( n^3 log e )
template<int mod> Matrix<mod> pow(Matrix<mod> A, int e) {
    return e == 0 ? identity<mod>(A.size())  :
    e % 2 == 0 ? pow(mul(A, A), e/2) : mul(A, pow(A, e-1));
}

template <typename T>
struct SegmentTree{
    using F = function<T(T,T)>;
    int n;
    F f;
    T ti;
    vector<T> dat;
    SegmentTree(){};
    SegmentTree(F f,T ti):f(f),ti(ti){}
    void init(int n_){
        n=1;
        while(n<n_) n<<=1;
        dat.assign(n<<1,ti);
    }
    void build(const vector<T> &v){
        int n_=v.size();
        init(n_);
        for(int i=0;i<n_;i++) dat[n+i]=v[i];
        for(int i=n-1;i;i--)
            dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
    }
    void set_val(int k,T x){
        dat[k+=n]=x;
        while(k>>=1)
            dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
    }
    //[a,b)
    T query(int a,int b,int k=1,int l=0,int r=-1){
        if(r<0)r=n;
        if(r<=a||b<=l) return ti;
        if(a<=l&&r<=b) return dat[k];
        T vl=query(a,b,k*2,l,(l+r)/2);
        T vr=query(a,b,k*2+1,(l+r)/2,r);
        return f(vl,vr);
    }
    T operator[](const int &k) const {return dat[k + n];}
};


struct HLDecomposition{
private:
    int t;
    void dfs_size(int v=0){
        size[v]=1;
        for(int& u:g[v]){
            if(par[u]>=0){
                swap(u,g[v].back());
                if(u==g[v].back())continue;
            }
            par[u]=v;
            dfs_size(u);
            size[v]+=size[u];
            if(size[u]>size[g[v][0]]){
                swap(u,g[v][0]);
            }
        }
    }
    void dfs_hld(int v=0){
        in[v] = t++;
        inv[in[v]]=v;
        for(int& u:g[v]){
            if(par[u]!=v)continue;
            head[u]=(u==g[v][0]?head[v]:u);
            dfs_hld(u);
        }
        out[v]=t;
    }
public:
    int V;
    vector<vector<int>> g;
    vector<int> dep,par,head,size,inv;
    vector<int> in,out;
    HLDecomposition(int size_)
    :t(0),V(size_),g(V),dep(V,0),par(V,-1),head(V),size(V),inv(V),in(V),out(V){}

    void add_edge(int u,int v){
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void build(int root=0){
        par[root]=0;
        dfs_size(root);
        par[root]=-1;
        dfs_hld(root);
    }

    int lca(int u,int v){
        while(1){
            if(in[u]>in[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)];
    }

    int operator[](const int &k){
        return in[k];
    }
};
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N;cin>>N;
  HLDecomposition hld(N);
  vector<tuple<ll,ll> >E(N-1);
  for(ll i=0;i<N-1;i++){
    ll a,b;cin>>a>>b;
    E[i]=make_tuple(a,b);
    hld.add_edge(a,b);
  }
  hld.build(0);
  //debugArray(hld,N);
  for(ll i=0;i<N-1;i++){
    ll a,b;
    tie(a,b)=E[i];
    if(hld.par[a]==b)swap(a,b);
    E[i]=make_tuple(a,b);
  }
  auto f=[](Matrix<MOD> a,Matrix<MOD> b){
    return mul(a,b);
  };
  SegmentTree<Matrix<MOD> > seg(f,identity<MOD>(2));
  seg.init(N);
  ll Q;cin>>Q;
  for(ll q=0;q<Q;q++){
    char op;cin>>op;
    if(op=='x'){
      ll i;
      Matrix<MOD> A(2,2);
      cin>>i>>A[0][0]>>A[0][1]>>A[1][0]>>A[1][1];
      seg.set_val(hld[get<1>(E[i])],A);
    }else{
      ll i,j;cin>>i>>j;
      Matrix<MOD> ans=identity<MOD>(2);
      while(1){
        if(hld[i]>hld[j])swap(i,j);
        if(hld.head[i]!=hld.head[j]){
          //debug(q);
          ans = mul(seg.query(hld[hld.head[j]],hld[j]+1),ans);
          j=hld.par[hld.head[j]];
        }else{
          if(i!=j)ans = mul(seg.query(hld[i]+1,hld[j]+1),ans);
          break;
        }
      }
      cout<<ans[0][0]<<" "<<ans[0][1]<<" "<<ans[1][0]<<" "<<ans[1][1]<<endl;
    }
  }

  return 0;
}
0