#278899 (C++11) No.235 めぐるはめぐる (5)

提出ソース
結果

問題	No.235 めぐるはめぐる (5)
ユーザー	lumc_
提出日時	2018-08-18 17:07:39
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	9,332 bytes
コンパイル時間	1,794 ms
コンパイル使用メモリ	172,488 KB
実行使用メモリ	35,184 KB
最終ジャッジ日時	2024-11-06 07:50:56
合計ジャッジ時間	21,774 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

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

raw source code
#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;

// require math library
/// ModInt Library {{{ ///
template<long long mod = (long long)1e9 + 7>
struct ModInt{
  long long val;
  ModInt() : val(0) {}
  ModInt(long long val) : val((val % mod + mod) % mod) {}
  operator int() const { return val; }
  operator long long() const { return val; }
  ModInt operator+(ModInt const &rhs) const {
    return ModInt(val + rhs.val);
  }
  ModInt operator-(ModInt const &rhs) const {
    return ModInt(val - rhs.val);
  }
  ModInt operator*(ModInt const &rhs) const {
    return ModInt(val * rhs.val);
  }
  ModInt operator/(ModInt const &rhs) const {
    return ModInt(val * rhs.inv().val);
  }
  ModInt &operator+=(ModInt const &rhs) {
    val = ((val + rhs.val) % mod + mod) % mod;
    return *this;
  }
  ModInt &operator-=(ModInt const &rhs) {
    val = ((val - rhs.val) % mod + mod) % mod;
    return *this;
  }
  ModInt &operator*=(ModInt const &rhs) {
    val = (val * rhs.val % mod + mod) % mod;
    return *this;
  }
  ModInt &operator/=(ModInt const &rhs) {
    val = (val * rhs.inv().val % mod + mod) % mod;
    return *this;
  }
  ModInt operator++(int) {
    ModInt tmp = *this;
    val = val + 1;
    if(val >= mod) val = 0;
    return tmp;
  }
  ModInt operator--(int) {
    ModInt tmp = *this;
    val = val == 0 ? mod - 1 : val - 1;
    return tmp;
  }
  ModInt &operator++() {
    val = val + 1;
    if(val >= mod) val = 0;
    return *this;
  }
  ModInt &operator--() {
    val = val == 0 ? mod - 1 : val - 1;
    return *this;
  }
  template<typename T> ModInt operator+(T const &rhs) const {
    return ModInt(val + rhs % mod);
  }
  template<typename T> ModInt operator-(T const &rhs) const {
    return ModInt(val - rhs % mod);
  }
  template<typename T> ModInt operator*(T const &rhs) const {
    return ModInt(val * (rhs % mod));
  }
  template<typename T> ModInt operator/(T const &rhs) const {
    return ModInt(val * modinv(rhs, mod));
  }
  template<typename T> ModInt &operator+=(T const &rhs) {
    val = ((val + rhs % mod) % mod + mod) % mod;
    return *this;
  }
  template<typename T> ModInt &operator-=(T const &rhs) {
    val = ((val - rhs % mod) % mod + mod) % mod;
    return *this;
  }
  template<typename T> ModInt &operator*=(T const &rhs) {
    val = (val * (rhs % mod) % mod + mod) % mod;
    return *this;
  }
  template<typename T> ModInt &operator/=(T const &rhs) {
    val = (val * modinv(rhs, mod) % mod + mod) % mod;
    return *this;
  }
  ModInt inv() const {
    return ModInt(modinv(val, mod));
  }
  friend ostream &operator<<(ostream &os, ModInt const &mv) { os << mv.val; return os; }
  friend constexpr ModInt operator+(long long a, ModInt const &mv) { return ModInt(a % mod + mv.val); }
  friend constexpr ModInt operator-(long long a, ModInt const &mv) { return ModInt(a % mod - mv.val); }
  friend constexpr ModInt operator*(long long a, ModInt const &mv) { return ModInt(a % mod * mv.val); }
  friend constexpr ModInt operator/(long long a, ModInt const &mv) { return ModInt(a % mod * mv.inv().val); }
};
/// }}}-- ///

using Int = ModInt<mod>;

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

template<class T>
struct StarrySkyTree {
  int n;
  vector<T> data;
  vector<T> all;
  vector<T> 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];
  }
  void act(int a, int b, T 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) +
      all[k * 2 + 2] * getRangeB((l + r) >> 1, r);
  }
  T getRangeB(int l, int r) {
    T res = bsum[r - 1];
    if(l - 1 >= 0) res -= bsum[l - 1];
    return res;
  }
  const T identity = 0;
  T 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];
    if(a <= l && r <= b) return sum * getRangeB(l, r) + data[k];
    return
      query(a, b, l, (l + r) >> 1, k * 2 + 1, sum) +
      query(a, b, (l + r) >> 1, r, k * 2 + 2, sum);
  }
};

// }}}

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 = max(vid[head[lo]], vid[hi]);
    f(nex + (nex == vid[hi] && !inclusive), vid[lo] + 1);
    lo = par[head[lo]];
  }
}

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<Int> k(n);
  for(int i = 0; i < n; i++) k[vid[i]] = c[i];
  StarrySkyTree<Int> qina(begin(k), end(k));
  vector<Int> 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];
  }
  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]);
      Int res = 0;
      auto f = [&](int l, int r) {
        // dump("?", q, l, r);
        res += qina.query(l, r);
        res += ecas[r - 1];
        if(l - 1 >= 0) res -= ecas[l - 1];
      };
      que(lc, s, f), que(lc, t, f, 0);
      cout << res << endl;
    }
  }
  return 0;
}
yukicoder

結果

テストケース

ソースコード
