結果

問題 No.650 行列木クエリ
ユーザー どららどらら
提出日時 2018-02-10 02:48:44
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 184 ms / 2,000 ms
コード長 5,016 bytes
コンパイル時間 2,193 ms
コンパイル使用メモリ 192,880 KB
実行使用メモリ 45,368 KB
最終ジャッジ日時 2024-10-09 16:15:50
合計ジャッジ時間 4,456 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 70 ms
11,672 KB
testcase_02 AC 184 ms
45,368 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 69 ms
11,376 KB
testcase_05 AC 182 ms
44,140 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 60 ms
8,060 KB
testcase_09 AC 130 ms
25,272 KB
testcase_10 AC 2 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

#define MOD 1000000007

struct ST {
  ll x, y, z, w;
  ST():x(1),y(0),z(0),w(1){}
  ST(ll x, ll y, ll z, ll w):x(x),y(y),z(z),w(w){}
};
ST combine(const ST& lhs, const ST& rhs){
  ST st;
  st.x = (lhs.x * rhs.x + lhs.y * rhs.z)%MOD;
  st.y = (lhs.x * rhs.y + lhs.y * rhs.w)%MOD;
  st.z = (lhs.z * rhs.x + lhs.w * rhs.z)%MOD;
  st.w = (lhs.z * rhs.y + lhs.w * rhs.w)%MOD;
  return st;
}
template<class S>
class SegmentTree {
  int N;
  vector<S> t;
  void build(){
    for(int i=N-1; i>0; i--){
      t[i] = combine(t[i<<1], t[i<<1|1]);
    }
  }
public:
  SegmentTree(int n_){
    N = 1;
    while(N < n_) N *= 2;
    t.resize(2*N);
    for(int i=N; i<2*N; i++){
      t[i] = S();
    }
    build();
  }
  SegmentTree(const vector<S>& v){
    N = 1;
    while(N < v.size()) N *= 2;
    t.resize(2*N);
    for(int i=0; i<v.size(); i++){
      t[i+N] = v[i];
    }
    build();
  }
  void modify(int p, S val){
    for(t[p+=N] = val; p>>=1;){
      t[p] = combine(t[p<<1], t[p<<1|1]);
    }
  }
  S query(int l, int r){
    S resl, resr;
    for(l+=N, r+=N; l<r; l>>=1, r>>=1){
      if(l&1) resl = combine(resl, t[l++]);
      if(r&1) resr = combine(t[--r], resr);
    }
    return combine(resl, resr);
  }
};



struct HLpath {
  int parent;
  vector<int> v;
  HLpath(int parent, int now):parent(parent){
    v.push_back(now);
  }
};

class HLDecomposition {
  int N;
  vector<vector<pair<int,int>>> G;
  vector<int> num;
  
  int dfs(int v, int p){
    if(num[v] != 0) return num[v];
    int sum = 1;
    int mx = -1, mxi = -1;
    rep(i,G[v].size()){
      if(G[v][i].first == p) continue;
      int res = dfs(G[v][i].first, v);
      if(mx < res){
        mx = res;
        mxi = i;
      }
      sum += res;
    }
    if(mxi>=0) G[v][mxi].second = 1;
    return num[v] = sum;
  }
public:
  HLDecomposition(int N):N(N),G(N),num(N){}

  void add_edge(int a, int b){
    G[a].push_back(make_pair(b,0));
    G[b].push_back(make_pair(a,0));
  }
  
  vector<HLpath> decomp(int root){
    dfs(root, -1);

    vector<HLpath> ret;
    queue<HLpath> que;
    que.push(HLpath(-1,root));
    while(!que.empty()){
      HLpath path = que.front(); que.pop();
      int p = path.parent;
      int now = path.v[0];
      int next = 0;
      while(next != -1){
        next = -1;
        rep(i,G[now].size()){
          if(G[now][i].first == p) continue;
          if(G[now][i].second == 1){
            path.v.push_back(G[now][i].first);
            next = G[now][i].first;
          }else{
            que.push(HLpath(now,G[now][i].first));
          }
        }
        p = now;
        now = next;
      }
      ret.push_back(path);
    }
    return ret;
  }
};


int main(){
  int n;
  cin >> n;

  vector<pair<int,int>> edges;
  HLDecomposition hld(n);

  rep(i,n-1){
    int a, b;
    cin >> a >> b;
    hld.add_edge(a,b);
    edges.push_back(make_pair(a,b));
  }

  vector<HLpath> ret = hld.decomp(0);
  vector<pair<int,int>> pos(n);
  vector<SegmentTree<ST>> sts(ret.size(), SegmentTree<ST>(0));

  /*
  rep(i,ret.size()){
    cout << i << "\t" << ret[i].parent << ": ";
    rep(j,ret[i].v.size()) cout << ret[i].v[j] << " "; cout << endl;
  }
   */
  
  rep(i,ret.size()){
    rep(j,ret[i].v.size()) pos[ret[i].v[j]] = make_pair(i,j);
    sts[i] = SegmentTree<ST>(ret[i].v.size()+5);
  }

  int q;
  cin >> q;
  rep(i,q){
    string type;
    cin >> type;
    if(type == "x"){
      int ei;
      cin >> ei;
      ll x, y, z, w;
      cin >> x >> y >> z >> w;
      int a = edges[ei].first;
      int b = edges[ei].second;
      int pa = (pos[a].second==0)?ret[pos[a].first].parent:ret[pos[a].first].v[pos[a].second-1];
      if(pa == b){
        sts[pos[a].first].modify(pos[a].second, ST(x,y,z,w));
      }else{
        sts[pos[b].first].modify(pos[b].second, ST(x,y,z,w));
      }
    }else{
      int f, t;
      cin >> f >> t;
      //cout << "\t" << pos[f].first << "\t" << pos[t].first << endl;
      if(pos[f].first == pos[t].first){
        int a = pos[f].second+1, b = pos[t].second+1;
        ST st = sts[pos[f].first].query(a,b);
        cout << st.x << " " << st.y << " " << st.z << " " << st.w << endl;
      }else{
        ST st;
        int nowi = pos[t].first;
        int p = pos[t].second+1;
        while(pos[f].first != nowi){
          ST tmp = sts[nowi].query(0,p);
          ST prod = combine(tmp, st);
          st = prod;
          p = pos[ret[nowi].parent].second+1;
          nowi = pos[ret[nowi].parent].first;
        }
        if(pos[f].second != p){
          ST tmp = sts[nowi].query(pos[f].second+1, p);
          ST prod = combine(tmp, st);
          st = prod;
        }
        cout << st.x << " " << st.y << " " << st.z << " " << st.w << endl;
      }
    }
  }
  
  return 0;
}
0