結果

問題 No.650 行列木クエリ
ユーザー tnakao0123tnakao0123
提出日時 2018-02-17 17:04:28
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 4,994 bytes
コンパイル時間 1,577 ms
コンパイル使用メモリ 112,768 KB
実行使用メモリ 20,840 KB
最終ジャッジ日時 2023-09-06 17:49:09
合計ジャッジ時間 2,313 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
14,796 KB
testcase_01 AC 29 ms
16,096 KB
testcase_02 AC 71 ms
20,840 KB
testcase_03 AC 5 ms
14,856 KB
testcase_04 AC 32 ms
16,080 KB
testcase_05 AC 72 ms
20,748 KB
testcase_06 AC 4 ms
14,856 KB
testcase_07 AC 3 ms
14,920 KB
testcase_08 AC 26 ms
16,184 KB
testcase_09 AC 52 ms
19,908 KB
testcase_10 AC 5 ms
14,776 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 650.cc: No.650 行列木クエリ - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int MAX_K = 18;
const int MAX_E2 = 1 << 18;
const long long MOD = 1000000007;

/* typedef */

typedef long long ll;
typedef queue<int> qi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

struct Mat {
  ll x00, x01, x10, x11;
  Mat(): x00(1), x01(0), x10(0), x11(1) {}
  Mat(ll _x00, ll _x01, ll _x10, ll _x11):
    x00(_x00), x01(_x01), x10(_x10), x11(_x11) {}

  void unit() { x00 = x11 = 1, x01 = x10 = 0; }
  void set(ll _x00, ll _x01, ll _x10, ll _x11) {
    x00 = _x00, x01 = _x01, x10 = _x10, x11 = _x11;
  }

  Mat operator*(const Mat &m) const {
    return Mat((x00 * m.x00 + x01 * m.x10) % MOD,
	       (x00 * m.x01 + x01 * m.x11) % MOD,
	       (x10 * m.x00 + x11 * m.x10) % MOD,
	       (x10 * m.x01 + x11 * m.x11) % MOD);
  }

  void print() { printf("%lld %lld %lld %lld\n", x00, x01, x10, x11); }
};

template <typename T, const int MAX_E2>
struct SegTreeMul {
  int n, e2;
  T nodes[MAX_E2], one;
  SegTreeMul() {}

  void init(int _n, T _one) {
    n = _n;
    one = _one;
    for (e2 = 1; e2 < n; e2 <<= 1);
    fill(nodes, nodes + MAX_E2, one);
  }

  T get(int i) { return nodes[e2 - 1 + i]; }

  void set(int i, T v) {
    int j = e2 - 1 + i;
    nodes[j] = v;
    j = (j - 1) / 2;

    for (;;) {
      nodes[j] = nodes[j * 2 + 1] * nodes[j * 2 + 2];
      if (j == 0) break;
      j = (j - 1) / 2;
    }
  }

  T mul_range(int r0, int r1, int k, int i0, int i1) {
    if (r1 <= i0 || i1 <= r0) return one;
    if (r0 <= i0 && i1 <= r1) return nodes[k];

    int im = (i0 + i1) / 2;
    T v0 = mul_range(r0, r1, k * 2 + 1, i0, im);
    T v1 = mul_range(r0, r1, k * 2 + 2, im, i1);

    return v0 * v1;
  }
  T mul_range(int r0, int r1) { return mul_range(r0, r1, 0, 0, e2); }
};

/* global variables */

vpii nbrs[MAX_N];
SegTreeMul<Mat,MAX_E2> st;
int prts[MAX_N], peis[MAX_N], cns[MAX_N], szs[MAX_N];
int sids[MAX_N], gtvs[MAX_N], gtes[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n - 1; i++) {
    int ai, bi;
    scanf("%d%d", &ai, &bi);
    nbrs[ai].push_back(pii(bi, i));
    nbrs[bi].push_back(pii(ai, i));
  }

  prts[0] = peis[0] = -1;
  qi q;
  q.push(0);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    int &up = prts[u];

    vpii &nbru = nbrs[u];
    for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
      int &v = vit->first, &ve = vit->second;
      if (v != up) {
	cns[u]++;
	prts[v] = u;
	peis[v] = ve;
	q.push(v);
      }
    }
  }
  //for (int i = 0; i < n; i++) printf("%d ", cns[i]); putchar('\n');

  for (int i = 0; i < n; i++) {
    szs[i] = 1;
    if (cns[i] == 0) q.push(i);
  }

  while (! q.empty()) {
    int u = q.front(); q.pop();
    int &up = prts[u];
    if (up >= 0) {
      szs[up] += szs[u];
      if (--cns[up] == 0) q.push(up);
    }
  }
  //for (int i = 0; i < n; i++) printf("%d ", szs[i]); putchar('\n');

  for (vpii::iterator vit = nbrs[0].begin(); vit != nbrs[0].end(); vit++)
    q.push(vit->first);
  int sn = 0;
  gtvs[0] = -1;

  while (! q.empty()) {
    int u = q.front(); q.pop();
    int &up = prts[u], &uei = peis[u];

    sids[uei] = sn++;
    gtvs[u] = up;
    gtes[u] = uei;

    for (int cu = u; cu >= 0;) {
      int &cup = prts[cu];
      vpii &nbrcu = nbrs[cu];
      int maxsz = 0, maxi = -1;
      for (vpii::iterator vit = nbrcu.begin(); vit != nbrcu.end(); vit++) {
	int &v = vit->first;
	if (v != cup && maxsz < szs[v]) maxsz = szs[v], maxi = v;
      }
      if (maxi < 0) break;

      for (vpii::iterator vit = nbrcu.begin(); vit != nbrcu.end(); vit++) {
	int &v = vit->first;
	if (v != cup) {
	  if (v != maxi) q.push(v);
	  else {
	    int &vei = peis[v];
	    sids[vei] = sn++;
	    gtvs[v] = up;
	    gtes[v] = uei;
	  }
	}
      }
      cu = maxi;
    }
  }

  st.init(n - 1, Mat());
  
  int qn;
  scanf("%d", &qn);

  while (qn--) {
    char op[2];
    scanf("%s", op);

    if (op[0] == 'x') {
      int i;
      ll x00, x01, x10, x11;
      scanf("%d%lld%lld%lld%lld", &i, &x00, &x01, &x10, &x11);
      //printf("x %d %lld %lld %lld %lld\n", i, x00, x01, x10, x11);

      Mat mi(x00, x01, x10, x11);
      st.set(sids[i], mi);
    }
    else { // op[0] == 'g'
      int i, j;
      scanf("%d%d", &i, &j);
      //printf("g %d %d\n", i, j);

      Mat ma;
      while (gtvs[i] != gtvs[j]) {
	Mat mi = st.mul_range(sids[gtes[j]], sids[peis[j]] + 1);
	ma = mi * ma;
	j = gtvs[j];
      }

      if (i != j) {
	Mat mi = st.mul_range(sids[peis[i]] + 1, sids[peis[j]] + 1);
	ma = mi * ma;
      }

      ma.print();
    }
  }
  return 0;
}
0