結果

問題 No.235 めぐるはめぐる (5)
ユーザー Min_25Min_25
提出日時 2016-07-21 04:41:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 399 ms / 10,000 ms
コード長 6,815 bytes
コンパイル時間 2,262 ms
コンパイル使用メモリ 123,992 KB
実行使用メモリ 24,724 KB
最終ジャッジ日時 2024-11-14 19:47:25
合計ジャッジ時間 5,571 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 399 ms
23,796 KB
testcase_01 AC 188 ms
24,724 KB
testcase_02 AC 306 ms
24,076 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;

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

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, h = -1; w >= 0; w = h, ++len) {
        tree[w].id = id++; h = heavy[w]; tree[w].head = v;
        for (auto x : edges[w]) if (x != h && 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_t>
  void update(int v, int w, func_t func) {
    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)) {
        func(0, tree[v].id - ofs + 1, ofs, size);
        v = tree[hv].par;
        continue;
      }
      func(tree[w].id - ofs, tree[v].id - ofs + 1, ofs, size);
      break;
    }
  }
 
  // to do
  template <typename func_t>
  i64 query(int v, int w, func_t func) {
    i64 result = 0;
    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)) {
        result += func(0, tree[v].id - ofs + 1, ofs, size);
        v = tree[hv].par;
        continue;
      }
      result += func(tree[w].id - ofs, tree[v].id - ofs + 1, ofs, size);
      break;
    }
    return result % mod;
  }

  int N;
  const Edges& edges;
  vector<node> tree;
  vector<int> heavy;
};
Edges edges;

struct SegmentTree {
  struct node {
    using result_t = i64;
    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) {}

    result_t result() {
      return sum;
    };
    static node merge(const node& lhs, const node& rhs) {
      int b = add_mod(lhs.b, rhs.b);
      int sum = (lhs.sum + rhs.sum + i64(lhs.b) * lhs.lazy + i64(rhs.b) * rhs.lazy) % mod;
      return node(b, sum, 0);
    }
    int b, sum, lazy;
  };
  
  SegmentTree(int N) : buff_size(N) { buff = new node[2 * N]; }
  ~SegmentTree() { delete [] buff; }

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

  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] = node::merge(tree[2 * i + 0], tree[2 * i + 1]);
    }
  }

  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];
      int l = tree[k].lazy;
      if (l) {
        add(tree[2 * k + 0].lazy, l);
        add(tree[2 * k + 1].lazy, l);
        tree[k].sum = (tree[k].sum + i64(l) * tree[k].b) % mod;
        tree[k].lazy = 0;
      }
    }
  }

  void fix(int k) {
    tree[k] = node::merge(tree[2 * k + 0], tree[2 * k + 1]);
  }

  void update(int l, int r, int v, int o, int s) {
    reset(o, s);

    // to do
    l += size; r += size;
    propagate(l); propagate(r - 1);

    bool lup = false, rup = false;
    for (; l < r; l >>= 1, r >>= 1) {
      if (lup) fix(l - 1);
      if (rup) fix(r);
      if (l & 1) add(tree[l++].lazy, v), lup = true;
      if (r & 1) add(tree[--r].lazy, v), rup = true;
    }
    for (--l; l < r; l >>= 1, r >>= 1)  {
      if (lup) fix(l);
      if (rup) fix(r);
    }
    for (; l; l >>= 1) fix(l);
  }

  node::result_t 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 = node::merge(left, tree[l++]);
      if (r & 1) right = node::merge(tree[--r], right);
    }
    left = node::merge(left, right);
    return left.result();
  }

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

    rep(i, N) if (hld.tree[i].head < 0) {
      int o = hld.tree[i].id;
      int l = -hld.tree[i].head;
      auto next_v = [&](int v) { return hld.heavy[v]; };
      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 {
        int ans = hld.query(v, w, [&](int l, int r, int o, int s) { return tree.query(l, r, o, s); });
        put_int(ans);
      }
    }
  }
}

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