結果

問題 No.650 行列木クエリ
ユーザー HaarHaar
提出日時 2019-09-10 00:14:20
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 2,066 bytes
コンパイル時間 3,209 ms
コンパイル使用メモリ 208,508 KB
実行使用メモリ 28,916 KB
最終ジャッジ日時 2023-09-15 12:54:18
合計ジャッジ時間 4,884 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,808 KB
testcase_01 AC 66 ms
12,536 KB
testcase_02 AC 145 ms
21,516 KB
testcase_03 AC 5 ms
7,816 KB
testcase_04 AC 68 ms
12,476 KB
testcase_05 AC 152 ms
21,252 KB
testcase_06 AC 5 ms
7,584 KB
testcase_07 AC 5 ms
7,800 KB
testcase_08 AC 66 ms
14,196 KB
testcase_09 AC 132 ms
28,916 KB
testcase_10 AC 4 ms
7,576 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define L long long int
#define I int

using namespace std;
const L m = 1e9+7;
struct M{L a,b,c,d;};

M operator*(const M &x, const M &y){return{(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};}

const M u = {1,0,0,1};
const int MAX = 101000;
M S[MAX*4];
int s,z;
int n;
vector<vector<int>> T(MAX);
vector<int> sub(MAX,1), par(MAX,-1), H(MAX), id(MAX);
vector<pair<int,int>> E(MAX);

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

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

int d1(int cur, int p){
  par[cur] = p;
  int t = 0;
  for(auto &nxt : T[cur]){
    if(nxt == p) continue;
    sub[cur] += d1(nxt, cur);
    if(sub[nxt] > t){
      t = sub[nxt];
      swap(nxt, T[cur][0]);
    }
  }
  return sub[cur];
}

void d2(int cur, int &i){
  id[cur] = i++;
  for(auto &nxt : T[cur]){
    if(nxt == par[cur]) continue;
    H[nxt] = (nxt == T[cur][0] ? H[cur] : nxt);
    d2(nxt, i);
  }
}

void Q(int x, int y, const function<void(int,int)> &f){
  while(1){
    if(id[x] > id[y]) swap(x, y);
    if(H[x] == H[y]){
      if(x != y) f(id[x]+1, id[y]+1);
      return;
    }
    f(id[H[y]], id[y]+1);
    y = par[H[y]];
  }
}

int edgeid(int u, int v){
  return par[u]==v ? id[u] : id[v];
}

int main(){
  cin >> n;

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

  int q; cin >> q;

  d1(0,-1);
  int i=0;
  d2(0,i);

  while(q--){
    char c;cin>>c;
    if(c=='x'){
      I i,x,y,z,w;cin>>i>>x>>y>>z>>w;
      auto[a,b]=E[i];
      I k=edgeid(a,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;
    }
  }

  return 0;
}
0