結果

問題 No.235 めぐるはめぐる (5)
ユーザー te-shte-sh
提出日時 2017-07-19 14:33:14
言語 D
(dmd 2.106.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 8,242 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 145,156 KB
最終ジャッジ日時 2024-04-27 02:28:03
合計ジャッジ時間 1,106 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/internal/write.d(143): Error: cannot implicitly convert expression `obj` of type `const(FactorRing!(1000000007, false))` to `int`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/write.d(1239): Error: template instance `std.format.internal.write.formatValueImpl!(LockingTextWriter, FactorRing!(1000000007, false), char)` error instantiating
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/write.d(632):        instantiated from here: `formatValue!(LockingTextWriter, FactorRing!(1000000007, false), char)`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(1759):        instantiated from here: `formattedWrite!(LockingTextWriter, char, FactorRing!(1000000007, false))`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(4277):        instantiated from here: `write!(FactorRing!(1000000007, false), char)`
Main.d(103):        instantiated from here: `writeln!(FactorRing!(1000000007, false))`

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;

const mod = 10 ^^ 9 + 7;
alias FactorRing!mod mint;
alias SegmentTreeLazy!(mint, mint(0), "a + b") segtree;
alias CulSum!mint culSum;

void main()
{
  auto n = readln.chomp.to!size_t;

  auto s = new mint[](n), c = new mint[](n);
  auto rds = readln.chomp.splitter, rdc = readln.chomp.splitter;
  foreach (i; 0..n) {
    s[i] = rds.front.to!int; rds.popFront();
    c[i] = rdc.front.to!int; rdc.popFront();
  }

  auto tree = Tree(n);
  foreach (_; 0..n-1) {
    auto rd = readln.split.to!(size_t[]), a = rd[0]-1, b = rd[1]-1;
    tree.addEdge(a, b);
  }

  tree.rootify(0);
  tree.makePath(0);

  auto np = tree.paths.length;
  auto css = new culSum*[](np), csc = new culSum*[](np);
  auto stl = new segtree*[](np);
  foreach (i; 0..np) {
    css[i] = new culSum(s.indexed(tree.paths[i]).array);
    csc[i] = new culSum(c.indexed(tree.paths[i]).array);
    auto npi = tree.paths[i].length;
    stl[i] = new segtree(npi);
    stl[i].weight = *csc[i];
  }

  auto q = readln.chomp.to!size_t;
  foreach (_; 0..q) {
    auto rd = readln.chomp.splitter;
    auto km = rd.front.to!int; rd.popFront();
    auto x = rd.front.to!size_t-1; rd.popFront();
    auto y = rd.front.to!size_t-1; rd.popFront();

    auto lca = tree.lca(x, y);
    if (y == lca) swap(x, y);

    auto calc0(size_t u, size_t v, int z, bool includeU) {
      while (tree.path[u] != tree.path[v]) {
        auto d = tree.depthInPath(v);
        auto p = tree.path[v];
        (*stl[p])[0..d+1] += mint(z);
        v = tree.parent[tree.head[v]];
      }

      auto d1 = tree.depthInPath(u), d2 = tree.depthInPath(v);
      auto p = tree.path[u];
      if (includeU)
        (*stl[p])[d1..d2+1] += mint(z);
      else if (d1 < d2)
        (*stl[p])[d1+1..d2+1] += mint(z);
    }

    auto calc1(size_t u, size_t v, bool includeU) {
      auto r = mint(0);

      while (tree.path[u] != tree.path[v]) {
        auto d = tree.depthInPath(v);
        auto p = tree.path[v];
        r += (*stl[p])[0..d+1] + (*css[p])[0..d+1];
        v = tree.parent[tree.head[v]];
      }

      auto d1 = tree.depthInPath(u), d2 = tree.depthInPath(v);
      auto p = tree.path[u];
      if (includeU)
        r += (*stl[p])[d1..d2+1] + (*css[p])[d1..d2+1];
      else if (d1 < d2)
        r += (*stl[p])[d1+1..d2+1] + (*css[p])[d1+1..d2+1];

      return r;
    }

    switch (km) {
    case 0:
      auto z = rd.front.to!int;
      if (x == lca) {
        calc0(x, y, z, true);
      } else {
        calc0(lca, x, z, true);
        calc0(lca, y, z, false);
      }
      break;
    case 1:
      auto r = mint(0);
      if (x == lca) {
        r += calc1(x, y, true);
      } else {
        r += calc1(lca, x, true);
        r += calc1(lca, y, false);
      }
      writeln(r);
      break;
    default:
      assert(0);
    }
  }
}

struct CulSum(T)
{
  T[] buf;

  this(T[] a)
  {
    buf = new T[](a.length + 1);
    buf[1..$][] = a[];
    foreach (i; 0..a.length)
      buf[i+1] += buf[i];
  }

  T opSlice(size_t l, size_t r)
  {
    return buf[r] - buf[l];
  }
}

struct SegmentTreeLazy(T, T unit, alias pred = "a + b")
{
  import core.bitop, std.conv, std.functional, std.range;
  alias predFun = binaryFun!pred;
  enum Op { none, add };

  const size_t n, an;
  T[] buf, laz;
  Op[] op;

  CulSum!mint weight;

  this(size_t n)
  {
    this.n = n;
    an = (1 << ((n - 1).bsr + 1));
    buf = new T[](an * 2);
    laz = new T[](an * 2);
    op = new Op[](an * 2);
    static if (T.init != unit) {
      buf[] = unit;
    }
  }

  void propagate(size_t k, size_t nl, size_t nr)
  {
    if (op[k] == Op.none) return;

    size_t nm = (nl + nr) / 2;
    setLazy(op[k], laz[k], k*2,   nl, nm);
    setLazy(op[k], laz[k], k*2+1, nm, nr);

    op[k] = Op.none;
  }

  void setLazy(Op nop, T val, size_t k, size_t nl, size_t nr)
  {
    switch (nop) {
    case Op.add:
      buf[k] += val * weight[nl..nr];
      laz[k] = op[k] == Op.none ? val : laz[k] + val;
      op[k] = Op.add;
      break;
    default:
      assert(0);
    }
  }

  void addOpe(Op op, T val, size_t l, size_t r, size_t k, size_t nl, size_t nr)
  {
    if (nr <= l || r <= nl) return;

    if (l <= nl && nr <= r) {
      setLazy(op, val, k, nl, nr);
      return;
    }

    propagate(k, nl, nr);

    auto nm = (nl + nr) / 2;
    addOpe(op, val, l, r, k*2,   nl, nm);
    addOpe(op, val, l, r, k*2+1, nm, nr);

    buf[k] = predFun(buf[k*2], buf[k*2+1]);
  }

  void opSliceOpAssign(string op: "+")(T val, size_t l, size_t r)
  {
    addOpe(Op.add, val, l, r, 1, 0, an);
  }

  T summary(size_t l, size_t r, size_t k, size_t nl, size_t nr)
  {
    if (nr <= l || r <= nl) return unit;

    if (l <= nl && nr <= r) return buf[k];

    propagate(k, nl, nr);

    auto nm = (nl + nr) / 2;
    auto vl = summary(l, r, k*2,   nl, nm);
    auto vr = summary(l, r, k*2+1, nm, nr);

    return predFun(vl, vr);
  }

  T opSlice(size_t l, size_t r)
  {
    return summary(l, r, 1, 0, an);
  }

  pure size_t opDollar() const { return n; }
}

struct Tree
{
  import std.container;

  size_t n;
  size_t[][] adj;
  int[] size, depth;
  size_t[] head, parent, path;
  size_t[][] paths;

  this(size_t n)
  {
    this.n = n;
    adj = new size_t[][](n);
  }

  auto addEdge(size_t s, size_t t)
  {
    adj[s] ~= t;
    adj[t] ~= s;
  }

  auto rootify(size_t r)
  {
    parent = new size_t[](n);
    depth = new int[](n);
    depth[] = -1;

    struct UP { size_t u, p; }
    auto st1 = SList!UP(UP(r, r));
    auto st2 = SList!UP();
    while (!st1.empty) {
      auto up = st1.front, u = up.u, p = up.p; st1.removeFront();

      parent[u] = p;
      depth[u] = depth[p] + 1;

      foreach (v; adj[u])
        if (v != p) {
          st1.insertFront(UP(v, u));
          st2.insertFront(UP(v, u));
        }
    }

    size = new int[](n);
    size[] = 1;

    while (!st2.empty) {
      auto up = st2.front, u = up.u, p = up.p; st2.removeFront();
      size[p] += size[u];
    }

    head = new size_t[](n);
    head[] = n;

    struct US { size_t u, s; }
    auto st = SList!US(US(r, r));

    while (!st.empty) {
      auto us = st.front, u = us.u, s = us.s; st.removeFront();

      head[u] = s;
      auto z = n;
      foreach (v; adj[u])
        if (head[v] == n && (z == n || size[z] < size[v])) z = v;

      foreach (v; adj[u])
        if (head[v] == n) st.insertFront(US(v, v == z ? s : v));
    }
  }

  auto makePath(size_t r)
  {
    auto pathIndex = 0;
    path = new size_t[](n);

    auto q = DList!size_t(r);

    while (!q.empty) {
      auto u = q.front; q.removeFront();

      if (u == head[u]) {
        path[u] = pathIndex++;
        paths ~= [u];
      } else {
        path[u] = path[head[u]];
        paths[path[u]] ~= u;
      }

      foreach (v; adj[u])
        if (v != parent[u]) q.insertBack(v);
    }
  }

  auto depthInPath(size_t n)
  {
    return depth[n] - depth[head[n]];
  }

  auto lca(size_t u, size_t v)
  {
    while (head[u] != head[v])
      if (depth[head[u]] < depth[head[v]]) v = parent[head[v]];
      else                                 u = parent[head[u]];
    return depth[u] < depth[v] ? u : v;
  }
}

struct FactorRing(int m, bool pos = false)
{
  long v;

  @property int toInt() { return v.to!int; }
  alias toInt this;

  this(T)(T _v) { v = mod(_v); }

  ref FactorRing!(m, pos) opAssign(int _v)
  {
    v = mod(_v);
    return this;
  }

  pure auto mod(long _v) const
  {
    static if (pos) return _v % m;
    else return (_v % m + m) % m;
  }

  pure auto opBinary(string op: "+")(long rhs) const { return FactorRing!(m, pos)(v + rhs); }
  pure auto opBinary(string op: "-")(long rhs) const { return FactorRing!(m, pos)(v - rhs); }
  pure auto opBinary(string op: "*")(long rhs) const { return FactorRing!(m, pos)(v * rhs); }

  pure auto opBinary(string op)(FactorRing!(m, pos) rhs) const
    if (op == "+" || op == "-" || op == "*") { return opBinary!op(rhs.v); }

  auto opOpAssign(string op: "+")(long rhs) { v = mod(v + rhs); }
  auto opOpAssign(string op: "-")(long rhs) { v = mod(v - rhs); }
  auto opOpAssign(string op: "*")(long rhs) { v = mod(v * rhs); }

  auto opOpAssign(string op)(FactorRing!(m, pos) rhs)
    if (op == "+" || op == "-" || op == "*") { return opOpAssign!op(rhs.v); }
}
0