結果

問題 No.386 貪欲な領主
ユーザー te-shte-sh
提出日時 2018-01-18 17:53:23
言語 D
(dmd 2.106.1)
結果
RE  
実行時間 -
コード長 3,516 bytes
コンパイル時間 934 ms
コンパイル使用メモリ 118,860 KB
実行使用メモリ 31,848 KB
最終ジャッジ日時 2024-06-12 23:35:05
合計ジャッジ時間 3,407 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,948 KB
testcase_04 AC 417 ms
30,348 KB
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 AC 391 ms
31,848 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.container; // SList, DList, BinaryHeap

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
T[] readArray(T)(size_t n){auto a=new T[](n),r=readln.splitter;foreach(ref v;a){v=r.front.to!T;r.popFront;}return a;}
T[] readArrayM(T)(size_t n){auto a=new T[](n);foreach(ref v;a)v=readln.chomp.to!T;return a;}

void main()
{
  int n; readV(n);

  auto g = Graph!int(n);
  foreach (i; 0..n-1) {
    int a, b; readV(a, b);
    g.addEdgeB(a, b);
  }
  auto tree = makeTree(g).rootify(0).doubling;

  auto u = readArrayM!long(n);

  auto v = new long[](n), q = DList!size_t(0);
  while (!q.empty) {
    auto s = q.front; q.removeFront();
    foreach (t; tree[s].filter!(t => t != tree.parent[s])) {
      v[t] = u[t] + v[s];
      q.insertBack(t);
    }
  }

  int m; readV(m);
  auto r = 0L;
  foreach (i; 0..m) {
    int a, b; long c; readV(a, b, c);
    auto l = tree.lca(a, b);
    r += (v[a] + v[b] - 2 * v[l] + u[l]) * c;
  }

  writeln(r);
}

struct Graph(N = int)
{
  import std.typecons;
  alias Node = N;
  Node n;
  Node[][] g;
  mixin Proxy!g;
  this(Node n) { this.n = n; g = new Node[][](n); }
  void addEdge(Node u, Node v) { g[u] ~= v; }
  void addEdgeB(Node u, Node v) { g[u] ~= v; g[v] ~= u; }
}

struct Tree(Graph)
{
  import std.algorithm, std.container, std.typecons;

  Graph g;
  mixin Proxy!g;
  alias Node = g.Node;
  Node root;
  Node[] parent;
  int[] size, depth;

  this(ref Graph g) { this.g = g; this.n = g.n; }

  ref auto rootify(Node r)
  {
    this.root = r;

    parent = new Node[](g.n);
    depth = new int[](g.n);
    depth[] = -1;

    struct UP { Node 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; g[u])
        if (v != p) {
          st1.insertFront(UP(v, u));
          st2.insertFront(UP(v, u));
        }
    }

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

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

    return this;
  }

  auto children(Node u) { return g[u].filter!(v => v != parent[u]); }
}

ref auto makeTree(Graph)(Graph g) { return Tree!Graph(g); }

struct Doubling(Tree)
{
  import std.algorithm, std.container, std.typecons, std.traits, core.bitop;
  alias Node = Tree.Node;

  Tree t;
  mixin Proxy!t;
  Node[][] ans;

  this(ref Tree t)
  {
    this.t = t;
    auto n = t.n;
    ans = new Node[][](n);
    foreach (i; 0..n) ans[i] = [t.parent[i]];

    auto q = SList!Node(t.root);
    while (!q.empty) {
      auto u = q.front; q.removeFront();
      for (auto i = 1, k = 2; k <= t.depth[u]; ++i, k <<= 1)
        ans[u] ~= ans[ans[u][i-1]][i-1];
      foreach (v; t[u].filter!(v => v != t.parent[u]))
        q.insertFront(v);
    }
  }

  auto ancestor(Node u, int k)
  {
    for (auto i = 0; k > 0; k >>= 1, ++i)
      if (k&1) u = ans[u][i];
    return u;
  }

  auto lca(Node u, Node v)
  {
    if (t.depth[u] > t.depth[v]) swap(u, v);
    if (u == t.root) return u;
    v = ancestor(v, t.depth[v]-t.depth[u]);
    if (u == v) return u;

    foreach_reverse (i; 0..t.depth[u].bsr+1)
      if (ans[u][i] != ans[v][i]) {
        u = ans[u][i];
        v = ans[v][i];
      }

    return t.parent[u];
  }
}

auto doubling(Tree)(Tree tree) { return Doubling!Tree(tree); }
0