結果

問題 No.650 行列木クエリ
ユーザー どららどらら
提出日時 2018-02-10 01:54:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,760 bytes
コンパイル時間 2,112 ms
コンパイル使用メモリ 189,448 KB
実行使用メモリ 45,264 KB
最終ジャッジ日時 2024-10-09 10:40:24
合計ジャッジ時間 3,609 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,888 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 4 ms
5,760 KB
testcase_08 AC 65 ms
10,748 KB
testcase_09 AC 139 ms
29,052 KB
testcase_10 WA -
権限があれば一括ダウンロードができます

ソースコード

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);
  }
};

int n;
vector<pair<int,int>> G[100005];
int num[100005];

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;
}

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

vector<HLpath> make_HLdecomposition(int root){
  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(){
  vector<pair<int,int>> edges;
  cin >> n;
  rep(i,n-1){
    int a, b;
    cin >> a >> b;
    G[a].push_back(make_pair(b,0));
    G[b].push_back(make_pair(a,0));
    edges.push_back(make_pair(a,b));
  }

  dfs(0,-1);
  vector<HLpath> ret = make_HLdecomposition(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+1);
          ST prod = combine(tmp, st);
          st = prod;
        }
        cout << st.x << " " << st.y << " " << st.z << " " << st.w << endl;
      }
    }
  }
  
  return 0;
}
0