結果

問題 No.235 めぐるはめぐる (5)
ユーザー akakimidoriakakimidori
提出日時 2019-07-10 12:23:45
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 1,132 ms / 10,000 ms
コード長 5,733 bytes
コンパイル時間 1,302 ms
コンパイル使用メモリ 34,944 KB
実行使用メモリ 15,596 KB
最終ジャッジ日時 2024-04-23 01:01:10
合計ジャッジ時間 6,791 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,132 ms
15,596 KB
testcase_01 AC 766 ms
15,592 KB
testcase_02 AC 1,045 ms
15,588 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))

const i32 mod = 1000000007;

typedef struct graph {
  i32 *v;
  i32 *next;
  i32 *start;
  i32 n;
  i32 p;
} graph;

void init_graph (graph *g) {
  for (i32 i = 0; i < g->n; ++i) {
    g->start[i] = -1;
  }
  g->p = 0;
}

graph* new_graph (i32 n, i32 e) {
  graph *g = ALLOC (1, graph);
  g->v = ALLOC (e, i32);
  g->next = ALLOC (e, i32);
  g->start = ALLOC (n, i32);
  g->n = n;
  g->p = 0;
  init_graph (g);
  return g;
}

void add_edge (graph *g, i32 a, i32 b) {
  i32 p = g->p;
  g->v[p] = b;
  g->next[p] = g->start[a];
  g->start[a] = p;
  g->p++;
}

void dfs_size (i32 v, graph *g, i32 *size, i32 *parent) {
  size[v] = 1;
  for (i32 p = g->start[v]; p != -1; p = g->next[p]) {
    i32 u = g->v[p];
    if (u == parent[v]) continue;
    parent[u] = v;
    dfs_size (u, g, size, parent);
    size[v] += size[u];
  }
}

void rooted (i32 root, graph *g, i32 *size) {
  i32 *parent = ALLOC (g->n, i32);
  parent[root] = root;
  dfs_size (root, g, size, parent);
  init_graph (g);
  for (i32 i = 0; i < g->n; ++i) {
    if (i == root) continue;
    add_edge (g, parent[i], i);
  }
  free (parent);
}

void dfs_HL (i32 v, graph *g, i32 *size, i32 *index, i32 *id, i32 *path_parent) {
  static i32 k = 0;
  index[v] = k++;
  if (g->start[v] != -1) {
    i32 hv = g->v[g->start[v]];
    for (i32 p = g->start[v]; p != -1; p = g->next[p]) {
      i32 u = g->v[p];
      if (size[u] > size[hv]) hv = u;
    }
    id[hv] = id[v];
    path_parent[hv] = path_parent[v];
    dfs_HL (hv, g, size, index, id, path_parent);
    for (i32 p = g->start[v]; p != -1; p = g->next[p]) {
      i32 u = g->v[p];
      if (u == hv) continue;
      id[u] = u;
      path_parent[u] = v;
      dfs_HL (u, g, size, index, id, path_parent);
    }
  }
}

typedef struct segment_tree {
  i32 *add;
  i32 *sum_c;
  i32 *sum_s;
  i32 size, bit;
} segment_tree;

segment_tree* new_segment_tree (i32 n, i32 *s, i32 *c, i32 *index) {
  i32 bit = 0;
  while ((1 << bit) < n) ++bit;
  segment_tree *seg = ALLOC (1, segment_tree);
  seg->add = ALLOC (2 << bit, i32);
  seg->sum_c = ALLOC (2 << bit, i32);
  seg->sum_s = ALLOC (2 << bit, i32);
  seg->size = 1 << bit;
  seg->bit = bit;
  for (i32 i = 0; i < n; ++i) {
    seg->sum_c[index[i] + seg->size] = c[i];
    seg->sum_s[index[i] + seg->size] = s[i];
  }
  for (i32 i = seg->size - 1; i > 0; --i) {
    seg->sum_c[i] = (seg->sum_c[2 * i] + seg->sum_c[2 * i + 1]) % mod;
    seg->sum_s[i] = (seg->sum_s[2 * i] + seg->sum_s[2 * i + 1]) % mod;
  }
  return seg;
}

i32 eval (segment_tree *s, i32 k) {
  return (s->sum_s[k] + (i64) s->add[k] * s->sum_c[k]) % mod;
}

void propagate (segment_tree *s, i32 x) {
  x += s->size;
  for (i32 i = s->bit; i > 0; --i) {
    i32 k = x >> i;
    s->add[2 * k] = (s->add[2 * k] + s->add[k]) % mod;
    s->add[2 * k + 1] = (s->add[2 * k + 1] + s->add[k]) % mod;
    s->add[k] = 0;
    s->sum_s[k] = (eval (s, 2 * k) + eval (s, 2 * k + 1)) % mod;
  }
}

void save (segment_tree *s, i32 x) {
  for (x = (x + s->size) >> 1; x > 0; x >>= 1) {
    s->sum_s[x] = (eval (s, 2 * x) + eval (s, 2 * x + 1)) % mod;
  }
}

void add (segment_tree *s, i32 l, i32 r, i32 v) {
  for (i32 x = l + s->size, y = r + s->size; x < y; x >>= 1, y >>= 1) {
    if (x & 1) {
      s->add[x] = (s->add[x] + v) % mod;
      x++;
    }
    if (y & 1) {
      --y;
      s->add[y] = (s->add[y] + v) % mod;
    }
  }
  save (s, l);
  save (s, r - 1);
}

i32 get_sum (segment_tree *s, i32 l, i32 r) {
  propagate (s, l);
  propagate (s, r - 1);
  i64 ans = 0;
  for (l += s->size, r += s->size; l < r; l >>= 1, r >>= 1) {
    if (l & 1) ans += eval (s, l++);
    if (r & 1) ans += eval (s, --r);
  }
  return ans % mod;
}

void run (void) {
  i32 n;
  scanf ("%" SCNi32, &n);
  i32 *s = ALLOC (2 * n, i32);
  i32 *c = s + n;
  for (i32 i = 0; i < 2 * n; ++i) {
    scanf ("%" SCNi32, s + i);
  }
  graph *g = new_graph (n, 2 * n);
  for (i32 i = 1; i < n; ++i) {
    i32 a, b;
    scanf ("%" SCNi32 "%" SCNi32, &a, &b);
    a--; b--;
    add_edge (g, a, b);
    add_edge (g, b, a);
  }
  i32 *size = ALLOC (n, i32);
  const i32 root = 0;
  rooted (root, g, size);
  i32 *index = ALLOC (n, i32);
  i32 *id = ALLOC (n, i32);
  i32 *path_parent = ALLOC (n, i32);
  id[root] = root;
  path_parent[root] = root;
  dfs_HL (root, g, size, index, id, path_parent);
  segment_tree *seg = new_segment_tree (n, s, c, index);
  i32 q;
  scanf ("%" SCNi32, &q);
  while (q--) {
    i32 op, x, y;
    scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32, &op, &x, &y);
    x--; y--;
    if (op == 0) {
      i32 z;
      scanf ("%" SCNi32, &z);
      while (id[x] != id[y]) {
        i32 rx = id[x];
        i32 ry = id[y];
        if (index[rx] > index[ry]) {
          add (seg, index[rx], index[x] + 1, z);
          x = path_parent[x];
        } else {
          add (seg, index[ry], index[y] + 1, z);
          y = path_parent[y];
        }
      }
      add (seg, MIN (index[x], index[y]), MAX (index[x], index[y]) + 1, z);
    } else {
      i64 ans = 0;
      while (id[x] != id[y]) {
        i32 rx = id[x];
        i32 ry = id[y];
        if (index[rx] > index[ry]) {
          ans += get_sum (seg, index[rx], index[x] + 1);
          x = path_parent[x];
        } else {
          ans += get_sum (seg, index[ry], index[y] + 1);
          y = path_parent[y];
        }
      }
      ans += get_sum (seg, MIN (index[x], index[y]), MAX (index[x], index[y]) + 1);
      ans %= mod;
      printf ("%" PRIi64 "\n", ans);
    }
  }
}

int main (void) {
  run();
  return 0;
}
0