結果

問題 No.235 めぐるはめぐる (5)
ユーザー Min_25Min_25
提出日時 2016-07-21 18:09:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 292 ms / 10,000 ms
コード長 6,865 bytes
コンパイル時間 1,727 ms
コンパイル使用メモリ 121,792 KB
実行使用メモリ 24,716 KB
最終ジャッジ日時 2024-04-27 02:21:45
合計ジャッジ時間 3,554 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 292 ms
23,828 KB
testcase_01 AC 126 ms
24,716 KB
testcase_02 AC 219 ms
23,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
// #pragma GCC target ("sse4") // SPOJ, codechef

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <functional>
#include <tuple>

#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

using Edges = vector< vector<int> >;

struct HLD {
  struct node {
    int id, par, head;
  };

  HLD(const Edges& edges) : N(edges.size()), edges(edges), tree(N), heavy(N) {
    dfs();
    path();
  }

  int dfs(int v=0, int p=-1) {
    int cnt = 1, x = 0, h = -1;
    for (auto w : edges[v]) if (w != p) {
      tree[w].par = v;
      int c = dfs(w, v);
      if (c > x) x = c, h = w;
      cnt += c;
    }
    heavy[v] = h;
    return cnt;
  }

  void path() {
    int id = 0;
    tree[id].par = -1;
    queue<int> que; que.push(id);
    while (!que.empty()) {
      int len = 0, v = que.front(); que.pop();
      for (int w = v; w >= 0; w = heavy[w], ++len) {
        tree[w].id = id++; tree[w].head = v;
        for (auto x : edges[w]) if (x != heavy[w] && x != tree[w].par) que.push(x);
      }
      tree[v].head = -len;
    }
  }

  int head(int v) const {
    return tree[v].head < 0 ? v : tree[v].head;
  }

  template <typename func>
  void update(int v, int w, func f) {
    while (1) {
      if (tree[v].id < tree[w].id) swap(v, w);
      int hv = head(v), ofs = tree[hv].id, size = -tree[hv].head;
      if (hv != head(w)) {
        f(0, tree[v].id - ofs + 1, ofs, size);
        v = tree[hv].par;
        continue;
      } else {
        f(tree[w].id - ofs, tree[v].id - ofs + 1, ofs, size);
        return;
      }
    }
  }

  template <typename func, typename node>
  node query(int v, int w, func f, node init) {
    node ret[2] = {init, init};
    while (1) {
      if (tree[v].id < tree[w].id) swap(v, w), swap(ret[0], ret[1]);
      int h = head(v), o = tree[h].id, s = -tree[h].head;
      if (head(v) != head(w)) {
        ret[0] = f(0, tree[v].id - o + 1, o, s).merge(ret[0]);
        v = tree[h].par;
        continue;
      } 
      return ret[1].reverse()
            .merge(f(tree[w].id - o, tree[v].id - o + 1, o, s))
            .merge(ret[0]);
    }
  }
  int N;
  const Edges& edges;
  vector<node> tree;
  vector<int> heavy;
};
Edges edges;

const int mod = 1e9 + 7;
int add_mod(int a, int b) {
  return (a += b - mod) < 0 ? a + mod : a;
}
void add(int& a, int b) {
  a = add_mod(a, b);
}

struct node {
  node() : b(0), sum(0), lazy(0) {}
  node(int a, int b) : b(b), sum(a), lazy(0) {}
  node(int b, int sum, int lazy) : b(b), sum(sum), lazy(lazy) {}

  int result() {
    return sum;
  };
  node reverse() const {
    return *this;
  }
  node merge(const node& rhs) const {
    int s = (sum + rhs.sum + i64(b) * lazy + i64(rhs.b) * rhs.lazy) % mod;
    return node(add_mod(b, rhs.b), s, 0);
  }
  void delay(int v) {
    add(lazy, v);
  }
  void propagate(node& left, node& right) {
    if (!lazy) return;
    add(left.lazy, lazy);
    add(right.lazy, lazy);
    sum = (sum + i64(lazy) * b) % mod;
    lazy = 0;
  }
  int b, sum, lazy;
};

struct SegmentTree {
  using node = ::node;

  SegmentTree(int N) : buff_size(N) { buff = new node[2 * N]; }
  ~SegmentTree() { delete [] buff; }

  template <typename func_t>
  void build(int v, int o, int s, int* A, int* B, func_t next_v) {
    reset(o, s);
    for (int i = 0; i < s; ++i, v = next_v(v)) tree[size + i] = node(A[v], B[v]);
    for (int i = s - 1; i > 0; --i) tree[i] = tree[2 * i + 0].merge(tree[2 * i + 1]);
  }

  // template

  void reset(int o, int s) {
    tree = buff + o * 2;
    size = s;
  }

  void propagate(int k) {
    int ks[30], ki = 0;
    for (k >>= 1; k >= 1; k >>= 1) ks[ki++] = k;
    for (; ki; ) {
      int k = ks[--ki];
      tree[k].propagate(tree[2 * k + 0], tree[2 * k + 1]);
    }
  }

  void merge(int k) {
    tree[k] = tree[2 * k + 0].merge(tree[2 * k + 1]);
  }

  void update(int l, int r, int v, int o, int s) {
    reset(o, s); l += size; r += size;
    propagate(l); propagate(r - 1);
    bool lup = false, rup = false;
    for (; l < r; l >>= 1, r >>= 1) {
      if (lup) merge(l - 1);
      if (rup) merge(r);
      if (l & 1) tree[l++].delay(v), lup = true;
      if (r & 1) tree[--r].delay(v), rup = true;
    }
    for (--l; l < r; l >>= 1, r >>= 1)  {
      if (lup) merge(l);
      if (rup) merge(r);
    }
    for (; l; l >>= 1) merge(l);
  }

  node query(int l, int r, int o, int s) {
    reset(o, s); l += size; r += size;
    propagate(l); propagate(r - 1);
    node left, right;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) left = left.merge(tree[l++]);
      if (r & 1) right = tree[--r].merge(right);
    }
    return left.merge(right);
  }

  int buff_size;
  node* buff;

  int size;
  node* tree;
};

const int N_MAX = 2e5 + 10;
int A[N_MAX];
int B[N_MAX];

#define getchar getchar_unlocked
#define putchar putchar_unlocked

// - 0.30 sec
int get_int() {
  int n, c;
  while ((c = getchar()) < '0') if (c == EOF) return -1;
  n = c - '0';
  while ((c = getchar()) >= '0') n = n * 10 + c - '0';
  return n;
}
// - 0.02 sec
void put_int(int n) {
  int res[11], i = 0;
  do { res[i++] = n % 10, n /= 10; } while (n);
  while (i) putchar(res[--i] + '0');
  putchar('\n');
}

void solve() {
  int N;
  while (~(N = get_int())) {
    edges.clear();
    edges.resize(N);

    rep(i, N) A[i] = get_int();
    rep(i, N) B[i] = get_int();
    rep(i, N - 1) {
      int v = get_int() - 1, w = get_int() - 1;
      edges[v].push_back(w);
      edges[w].push_back(v);
    }
    auto hld = HLD(edges);
    auto tree = SegmentTree(N);
    using node = SegmentTree::node;

    auto next_v = [&](int v) { return hld.heavy[v]; };
    rep(i, N) if (hld.tree[i].head < 0) {
      int o = hld.tree[i].id;
      int l = -hld.tree[i].head;
      tree.build(i, o, l, A, B, next_v);
    }

    int Q = get_int();
    rep(i, Q) {
      int c = get_int(), v = get_int() - 1, w = get_int() - 1;
      if (c == 0) {
        int z = get_int();
        hld.update(v, w, [&](int l, int r, int o, int s) { tree.update(l, r, z, o, s); });
      } else {
        auto ans = hld.query(v, w, 
          [&](int l, int r, int o, int s) { return tree.query(l, r, o, s); },
          node()
        );
        put_int(ans.result());
      }
    }
  }
}

int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}
0