結果

問題 No.235 めぐるはめぐる (5)
ユーザー lumc_lumc_
提出日時 2018-08-18 14:21:07
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 6,435 bytes
コンパイル時間 1,852 ms
コンパイル使用メモリ 171,288 KB
実行使用メモリ 30,080 KB
最終ジャッジ日時 2024-10-15 12:54:14
合計ジャッジ時間 16,093 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// #undef DEBUG
// #define DEBUG
/// {{{ DEBUG --- ///
#ifdef DEBUG
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << "{"; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; return o; }
#ifdef USE_COUT
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cout<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#else
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#endif
template<class T> inline void dump2D(T &d, size_t sizey, size_t sizex) { ostream&o=
#ifdef USE_COUT
  cout;
#else
  cerr;
#endif
  for(size_t i = 0; i < sizey; i++) { for(size_t j = 0; j < sizex; j++) o << d[i][j] << " "; o << endl; }
}
#else
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); return o; }
#define dump(...) (42)
#define dump2D(...) (42)
#endif
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
/// }}}--- ///

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll extgcd(ll a, ll b, ll &x, ll &y) { ll d; return b == 0 ? (x = 1, y = 0, a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d); }
ll modinv(ll a, ll mod = 1e9 + 7) { ll x = 0, y = 0; extgcd(a, mod, x, y); return (x + mod) % mod; }
ll modpow(ll a, ll b, ll mod = 1e9 + 7) { ll r = 1; a %= mod; while(b) { if(b & 1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; }

const ll mod = 1e9 + 7;
const int N = 2e5;
int n;

// a[i]に区間add
// 区間sum a[i] * b[i]
// を高速に求めたい
//
// {{{

struct StarrySkyTree {
  int n;
  vector<int> data;
  vector<int> all;
  vector<int> bsum;
  int topbit(int x) {
    x = x & 0xFFFF0000 ? x & 0xFFFF0000 : x;
    x = x & 0xFF00FF00 ? x & 0xFF00FF00 : x;
    x = x & 0xF0F0F0F0 ? x & 0xF0F0F0F0 : x;
    x = x & 0xCCCCCCCC ? x & 0xCCCCCCCC : x;
    x = x & 0xAAAAAAAA ? x & 0xAAAAAAAA : x;
    return x;
  }
  StarrySkyTree(int t) {
    n = topbit(t);
    if(n < t) n <<= 1;
    data.resize((n << 1) - 1);
    all.resize((n << 1) - 1);
    bsum.resize(n);
  }
  template<class InputIter, class = typename std::iterator_traits<InputIter>::value_type>
  StarrySkyTree(InputIter first, InputIter last)
  : StarrySkyTree(distance(first, last)) {
    copy(first, last, begin(bsum));
    for(int i = 1; i < n; i++) bsum[i] = (bsum[i - 1] + bsum[i]) % mod;
  }
  void act(int a, int b, ll x, int l = 0, int r = -1, int k = 0) {
    if(r < 0) r = n;
    if(b <= l || r <= a) return;
    if(a <= l && r <= b) {
      all[k] = all[k] + x;
      return;
    }
    act(a, b, x, l, (l + r) >> 1, k * 2 + 1);
    act(a, b, x, (l + r) >> 1, r, k * 2 + 2);
    data[k] = (data[k * 2 + 1] + data[k * 2 + 2] +
      all[k * 2 + 1] * getRangeB(l, (l + r) >> 1) % mod +
      all[k * 2 + 2] * getRangeB((l + r) >> 1, r) % mod) % mod;
  }
  ll getRangeB(int l, int r) {
    ll res = bsum[r - 1];
    if(l - 1 >= 0) res -= bsum[l - 1];
    return (res % mod + mod) % mod;
  }
  const ll identity = 0;
  ll query(int a, int b, int l = 0, int r = -1, int k = 0, ll sum = 0) {
    if(r < 0) r = n;
    if(b <= l || r <= a) return identity;
    sum = (sum + all[k]) % mod;
    if(a <= l && r <= b) return (sum % mod * getRangeB(l, r) % mod + data[k]) % mod;
    return (
      query(a, b, l, (l + r) >> 1, k * 2 + 1, sum) +
      query(a, b, (l + r) >> 1, r, k * 2 + 2, sum)) % mod;
  }
};

// }}}

ll s[N], c[N];

vector<int> g[N];

int head[N];
int sz[N];
int dep[N];
int par[N];
int vid[N];
int id = 0;

void dfs0(int i, int p, int d = 0) {
  par[i] = p;
  sz[i] = 1;
  dep[i] = d;
  for(int &j : g[i]) if(j != p) {
    dfs0(j, i, d + 1);
    sz[i] += sz[j];
    if(sz[j] > sz[g[i][0]]) {
      swap(g[i][0], j);
    }
  }
}

void dfs(int i, int p) {
  head[i] = i;
  vid[i] = id++;
  for(int j : g[i]) if(j != p) {
    dfs(j, i);
    if(j == g[i][0]) {
      head[j] = head[i];
    }
  }
}

int lca(int a, int b) {
  while(1) {
    if(vid[a] > vid[b]) swap(a, b);
    if(head[a] == head[b]) return a;
    b = par[head[b]];
  }
}

void que(int hi, int lo, function<void(int, int)> f, bool inclusive = true) {
  while(lo != -1 && dep[lo] >= dep[hi]) {
    int nex = head[lo];
    if(nex == -1 || dep[nex] < dep[hi]) nex = hi;
    f(vid[nex] + (nex == hi && !inclusive), vid[lo] + 1);
    lo = par[nex];
  }
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> s[i];
  for(int i = 0; i < n; i++) cin >> c[i];
  for(int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b; a--; b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  dfs0(0, -1);
  dfs(0, -1);
  vector<ll> k(n);
  for(int i = 0; i < n; i++) k[vid[i]] = c[i];
  StarrySkyTree qina(begin(k), end(k));
  vector<ll> ecas(n);
  for(int i = 0; i < n; i++) {
    ecas[vid[i]] = s[i];
  }
  for(int i = 1; i < n; i++) {
    ecas[i] = (ecas[i] + ecas[i - 1]) % mod;
  }
  int q;
  cin >> q;
  while(q--) {
    int c;
    cin >> c;
    if(c == 0) { // update
      int s, t, k;
      cin >> s >> t >> k;
      s--; t--;
      int lc = lca(s, t);
      dump(s, t, lc);
      auto f = [&](int l, int r) {
        dump("!", q, l, r);
        qina.act(l, r, k);
      };
      que(lc, s, f), que(lc, t, f, 0);
    } else { // ask
      int s, t;
      cin >> s >> t;
      s--; t--;
      int lc = lca(s, t);
      // dump(lc, s, t);
      // dump(dep[lc], dep[s], dep[t]);
      ll res = 0;
      auto f = [&](int l, int r) {
        dump("?", q, l, r);
        res += qina.query(l, r), res %= mod;
        res += ecas[r - 1], res %= mod;
        if(l - 1 >= 0) res -= ecas[l - 1], res %= mod;
      };
      que(lc, s, f), que(lc, t, f, 0);
      cout << (res % mod + mod) % mod << endl;
    }
  }
  return 0;
}

0