結果

問題 No.650 行列木クエリ
ユーザー HaarHaar
提出日時 2019-09-10 01:09:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 1,678 bytes
コンパイル時間 2,590 ms
コンパイル使用メモリ 207,272 KB
実行使用メモリ 27,972 KB
最終ジャッジ日時 2023-09-15 12:58:35
合計ジャッジ時間 4,094 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,928 KB
testcase_01 AC 65 ms
11,220 KB
testcase_02 AC 147 ms
20,476 KB
testcase_03 AC 5 ms
6,908 KB
testcase_04 AC 66 ms
11,192 KB
testcase_05 AC 146 ms
20,444 KB
testcase_06 AC 4 ms
6,696 KB
testcase_07 AC 4 ms
6,912 KB
testcase_08 AC 64 ms
12,656 KB
testcase_09 AC 132 ms
27,972 KB
testcase_10 AC 4 ms
6,932 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define L long long int
#define I int
#define R return
using namespace std;
const L m=1e9+7;
struct M{L a,b,c,d;};
M operator*(M x,M y){R{(x.a*y.a+x.b*y.c)%m,(x.a*y.b+x.b*y.d)%m,(x.c*y.a+x.d*y.c)%m,(x.c*y.b+x.d*y.d)%m};}
M u={1,0,0,1};
const I X=101000;
M S[X*4];
I s,z,n,q,o;
vector<vector<I>>T(X);
vector<I>B(X,1),P(X,-1),H(X),D(X);
pair<I,I>E[X];

M G(I x,I y,I i=0,I l=0,I r=s){
  if(r<=x||y<=l) R u;
  else if(x<=l&&r<=y) R S[i];
  R G(x,y,i*2+1,l,(l+r)/2)*G(x,y,i*2+2,(l+r)/2,r);
}

void U(I i,M x){
  I j=i+s-1;
  S[j--]=x;
  while(j>=0){
    S[j/2]=S[(j/2)*2+1]*S[(j/2)*2+2];
    (j/=2)--;
  }
}


I d1(I C,I p){
  P[C]=p;
  I t=0;
  for(auto&N:T[C]){
    if(N==p)continue;
    B[C]+=d1(N,C);
    if(B[N]>t){
      t=B[N];
      swap(N,T[C][0]);
    }
  }
  R B[C];
}

void d2(I C){
  D[C]=o++;
  for(auto&N:T[C]){
    if(N==P[C])continue;
    H[N]=(N==T[C][0]?H[C]:N);
    d2(N);
  }
}

void Q(I x,I y,function<void(I,I)>f){
  while(1){
    if(D[x]>D[y])swap(x,y);
    if(H[x]==H[y]){
      if(x!=y)f(D[x]+1,D[y]+1);
      R;
    }
    f(D[H[y]],D[y]+1);
    y=P[H[y]];
  }
}

I main(){
  cin>>n;

  s=1;
  while(s<n)s*=2;
  z=s*2-1;
  while(z--)S[z+1]=u;
  
  for(I i=0;i<n-1;++i){
    I a,b;cin>>a>>b;
    T[a].push_back(b);
    T[b].push_back(a);
    E[i]={a,b};
  }

  cin>>q;

  d1(0,-1);d2(0);

  while(q--){
    char c;cin>>c;
    if(c-'g'){
      I i,x,y,z,w;cin>>i>>x>>y>>z>>w;
      auto[a,b]=E[i];
      I k=P[a]==b?D[a]:D[b];
      U(k,{x,y,z,w});
    }else{
      I i,j;cin>>i>>j;
      M a=u;
      auto f=[&](I x, I y){a=G(x,y)*a;};
      
      Q(i,j,f);
      cout<<a.a<<" "<<a.b<<" "<<a.c<<" "<<a.d<<endl;
    }
  }

  R 0;
}
0