Luzhiled's memo

メモということです

パソコン甲子園2017 予選

出てないけど解いたのでPCK2017予選の解法を書きます

体感難易度としては
1 = 2 = 3 = 4 = 5 < 6 = 8 < 7 < 10 < 9 < 11
くらい

ほとんど考察だけの問題もあるので、一度考えてから見るのがおすすめ

Handsel (お年玉)

ジャッジ
Handsel | Aizu Online Judge

概要

1000 の倍数である数 a, b が与えられます。足し合わせて2で割った値を求めてください。

解法

a+b は必ず偶数になるので答えが少数になることはありません。問題文の通りに書くといいです。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;

  cout << (a + b) / 2 << endl;
}

Shopping (買い物)

ジャッジ
Shopping | Aizu Online Judge

概要

本が買いたいあなたは、友人とともに本屋に来ました。
あなたの所持金 m と友人の所持金 f、本の値段 b が与えられた時、友人から借りなくてはならない最小の金額を求めてください。
ただし、友人からいくら借りても本を買うことができない場合は NA を出力しなさい。

解法

m + f < b のとき、友人から全額借りても本は買えない、かつそれ以外の条件で本が買えない状況にはならないので、先の条件のとき答えはNA

そうでない場合、友人から借りる金額を最小にするのであれば自分が出来る限りお金を出すのが最適である。
b \leq mのとき、本の代金をすべて自分が出せるので答えは 0、そうじゃない場合はどうしても友人からお金を借りなくてはならないので答えは
b - m になる。

この問題はいろいろな解法があると思うので各自適当に読み替えてください

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int m, f, b;
  cin >> m >> f >> b;

  if (m + f < b) {
    cout << "NA" << endl;
  } else {

    if (b <= m) {
      cout << 0 << endl;
    } else {
      cout << b - m << endl;
    }
  }
}

Day of Week (９月Ｘ日)

ジャッジ
Day of Week | Aizu Online Judge

概要

2017年9月9日は土曜日である。
2017年9月の日にち X が与えられたとき、その日の曜日を答えなさい。

解法

曜日は7日周期で一周するので、7で割ったあまりを利用すると楽に実装ができます。

(実際には存在しないが)9月0日〜9月6日までが何曜日かを配列に記憶したあと、7で割ったあまりが何曜日かを出力すればいいです。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int x;
  cin >> x;

  vector<string> v{"thu", "fri", "sat", "sun", "mon", "tue", "wed"};

  cout << v[x % 7] << endl;
}

Reservation System (予約システム)

ジャッジ
Reservation System | Aizu Online Judge

概要

\left[a, b \right) *1の期間スーパーコンピュータを使いたい。
スーパーコンピュータにはすでにN件の予約が入っており、i (1 \leq i \leq N)件目の予約は\left[s, t \right)の間使用するというものである。
使いたい期間にかぶっている予約がある場合は1を、ない場合は0を出力しなさい。ただし、すでにある予約同士に重複はないものとする。

解法

(問題がわかりにくすぎませんか(小声))

i (1 \leq i \leq N)件目の予約が\left[a, b \right)とかぶっていないかどうかを条件分岐などで判断すればよい。
境界が少しややこしいのでそこだけ注意

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a, b;
  int n;

  cin >> a >> b >> n;

  bool ans = false;
  while (n--) {
    int s, t;
    cin >> s >> t;

    if (t <= a || b <= s)
      continue;
    ans = true;
  }

  cout << ans << endl;
}

Wire (電線)

ジャッジ
Wire | Aizu Online Judge

概要

(概要にするのがむずかしいので問題よんで♡)


解法

パネルの幅が2mであるとかは実際には関係ないのでこれ以降は無視するものとする。

簡単化のために、縦の線のみがある場合と横の線のみがある場合でそれぞれ交点がいくつあるかを考える。

縦の線のみがある場合、交点は端にあるものも含め x + 1 個、横の線のみがある場合も同様に y + 1 個の交点が存在する。

同じ座標の交点は1つとしてカウントしなくてはならない。これは gcd(x, y) + 1 個*2存在するはずなので、それを (x + 1) + (y + 1) から引いたものが答えになる。

(x + 1) + (y + 1) - (gcd(x, y) + 1) = x + y - gcd(x, y) + 1 をそのまま実装するとよい。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int x, y;
  cin >> x >> y;

  cout << x + y - __gcd(x, y) + 1 << endl;
}

Trampoline (トランポリン)

ジャッジ
Trampoline | Aizu Online Judge

概要

N 個のトランポリンが一直線上に10m間隔で並んでおり、それぞれのトランポリンについて、水平方向に跳ぶことができる最大距離が決まっています。
トランポリンから一度も降りず、左端のトランポリンと右端のトランポリンの間を往復することができるか答えなさい。

解法

「左端から右端に行けるか」と「右端から左端に行けるか」という問題を解く必要がある。
各トランポリンが跳ぶことのできる最大距離をもった配列を左右逆転させると、「右端から左端に行けるか」という問題は「左端から右端に行けるか」という問題と同じになるので、以降はこれを考える。

トランポリン i から距離 d_i 以内にあるトランポリンには自由に行けることを考えると、現在到達できるトランポリンのうち最も遠くまで行けるトランポリンに飛び移り、その最大距離を貪欲に伸ばしていく方法が思いつく。
到達できるかをboolの配列などで管理してしまうとO(N^2)になってしまうが、すでに見た区間から跳ぶことのできる最大距離は変わらないのでこれを無視すればいい。
しゃくとりみたいな感じでやると楽。

また、10m間隔であることを考えるのはややこしいので、跳ぶことのできる最大距離はあらかじめ10で割って管理すると楽に実装ができる。


解説が雑でごめんなさい……


コード

#include <bits/stdc++.h>
using namespace std;

bool izryt(vector<int> &v) {
  int d = 0;
  bool res = true;
  for (int i = 0; i < v.size(); ++i) {
    if (i > d) {
      res = false;
      break;
    }

    d = max(d, i + v[i]);
  }

  return res;
}

int main() {
  int n;
  cin >> n;

  vector<int> d(n);
  for (auto &i : d)
    cin >> i;
  for (auto &i : d)
    i /= 10;

  bool ans = true;
  if (!izryt(d))
    ans = false;
  reverse(d.begin(), d.end());
  if (!izryt(d))
    ans = false;

  cout << (ans ? "yes" : "no") << endl;
}

Loading (積み荷の配置)

ジャッジ
Loading | Aizu Online Judge

概要

縦 H マス、横 4 マスの上に 大きさ1\times 1 である N 個の荷物を置けないマスがある。
ここに新たに大きさ 2 \times 2 であるような荷物を積みたい。最大でいくつ積めるか。
ただし、マスをまたいで積んだり、荷物を傾けて積むことはできない。

解法

めっちゃ貪欲に見えるが、そこをぐっとこらえてDPをする。
横が4マスで固定であることを考えると、荷物の置き方は

xxxx
xxxx

ooxx
ooxx

xoox
xoox

xxoo
xxoo

oooo
oooo

の5通りだけである。(oの位置に荷物を積むイメージ)
荷物を置く場所は左、真ん中、右の3通りだけなので、これをbitで管理してbitDPをするといい。

今は上から何番目の行か、今の状態でどこにおけるか、の2つの状態をもち、次の状態でどこにおけるかをbitとして渡すメモ化再帰でといた

コード

#include <bits/stdc++.h>
using namespace std;

int h, n;
vector<int> b;

int dp[101010][10];

int dfs(int i = 1, int bit = 0) {
  if (i == h) {
    return 0;
  }
  bit |= b[i];

  int &ret = dp[i][bit];
  if (~ret)
    return ret;

  ret = 0;
  if (bit == 0)
    ret = max(ret, dfs(i + 1, 0b111) + 2);
  if ((bit & (0b100)) == 0)
    ret = max(ret, dfs(i + 1, 0b110) + 1);
  if ((bit & (0b010)) == 0)
    ret = max(ret, dfs(i + 1, 0b111) + 1);
  if ((bit & (0b001)) == 0)
    ret = max(ret, dfs(i + 1, 0b011) + 1);
  ret = max(ret, dfs(i + 1, 0));

  return ret;
}

int main() {
  memset(dp, -1, sizeof(dp));
  cin >> h >> n;

  int ei[4] = {0b100, 0b110, 0b011, 0b001};
  b.assign(h + 1, 0);
  for (int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    b[y + 1] |= ei[x];
    b[y] |= ei[x];
  }

  cout << dfs() << endl;
}

Dungeon (ダンジョン)

ジャッジ
Dungeon | Aizu Online Judge

概要

最初マス (0, 0) にいるキャラクターのボムボムくんを操作し、ゲーム内にいるN体の敵を倒したい。
ボムボムくんは以下の2つの操作ができる。

  • 上下左右に1マス動く
  • 爆弾を使用し、ボムボムくんと同じ行、列にいる敵をすべて倒す

ボムボムくんはマスを移動するのにコストが1かかる。爆弾の使用回数に制限はなく、コストもかからない。
すべての敵を倒すのに必要なコストの最小値を求めよ。

解法

問題の位置がさすがに悪いと思います……

爆弾の使用制限はなく、コストもかからないので、別に敵がいなくてもバンバン爆弾を爆発させるものとして考えます。こう考えると、ボムボムくんの上下左右に入った段階で敵は死ぬものとみなせるので簡単化につながります(？)

最初にボムボムくんをまっすぐ下方向にi(0\leq i \leq N)マス進ませ、残った敵がすべていなくなるまで横方向に進む、という操作を考えます。
i 行目までの敵は一度以上ボムボムくんと同じ行に存在していたはずなので無視、i + 1 ~ H 行にいる敵を倒すには横に移動するしかないので、その区間にいる敵の x 座標の最大値がすべての敵を倒すために必要な横移動のコストになります。
よって、すべての敵を倒すのに必要なコストはi + max(0, x_{i + 1}, x_{i + 1}, ..., x_{H})で求められます。(ここで x_i (0 \leq i \leq H) は、i 行目にいる敵の x 座標の最大値、存在しなければ0 だとします。)

下に何マス進むかをforループなどで決め打ちでO(H)、それよりも下にいる敵の x 座標の最大値の取得はセグメント木などで取得すると O(lg(H)) になり、合計で O(H lg(H) となり、この問題が解けました

が、i 行目より下にいる敵の x 座標の最大値は単調減少になっているので、i の決め打ちを H から順に1つずつ小さくしていくと、それより下にいる敵の x 座標の最大値は O(1) で求められる上にセグメント木も不要なので楽に実装ができます。



積荷の配置やトランポリンよりよっぽど簡単なんじゃないかな……


コード

#include <bits/stdc++.h>
using namespace std;

const int inf = 1001001001;

int main() {
  int w, h, n;
  cin >> w >> h >> n;

  vector<int> a(h + 2, 0);

  for (int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;

    a[y] = max(a[y], x);
  }

  int ans = inf;
  for (int i = h; i >= 0; --i) {
    ans = min(ans, i + a[i + 1]);
    a[i] = max(a[i], a[i + 1]);
  }

  cout << ans << endl;
}

Swapping Characters (文字列スワップ)

ジャッジ
Swapping Characters | Aizu Online Judge

概要

文字列 s が与えられる。隣接する任意の2文字の交換を k 回以内行い作ることのできる辞書順最小の文字列を求めよ。

解法

問題の言い換えをすると、

文字列 s の中からi*3 番目の文字取り出す時に、コストがiかかります。コストの合計が k 以内になるように文字を取り出し、新たな文字列 t の末尾に追加する操作を繰り返し、辞書順最小の文字列を構成してください。という問題になります。

うしさんがわかりやすくしてくれました。ありがとうございます。

説明の省略のために、以下では N を文字列 s の文字数としています。

現在使えるコストが k だとすると、残っている文字列の中の先頭 k 文字にある文字のうち、辞書順最小の文字を貪欲にとっていくのが最適です。また、先頭 k 文字に同一の文字が存在する場合はより先頭の方からとってくるのが最適になることもわかります。

文字列から実際に1文字ずつ削除してしまうと、それだけで O(N^2) かかってしまうので間に合いません。
そこで、文字列中にまだ存在するなら 1 を、すでに使われた時には 0 とする数列を持つことを考えます。
この数列の累積和が k 以上となるような最小のindexを r とすると、現在取れる文字は、最初の文字列中の \left[ 0, r \right) にある文字であることがわかります。

累積和は一回の操作ごとに変更が加えられるので、Binary Indexed Tree (Fenwic Tree) を使い高速化しましょう。
数列の累積和が k 以上となるような最小のindex r は、累積和を二分探索をすることで求められます。
愚直にやるとO(lg^2N) となってしまいやや遅いですが、二分探索で使いたい情報はBIT上で左右のノードに持っていることを利用して O(lgN) に抑えることができます。

(詳しいやり方は http://hos.ac/slides/20140319_bit.pdf の最後の方にあります)

r さえ求められれば、あとはセグメント木などを用いてその区間の最小の文字列を取得、その場所はそれ以降使えないので 'z' よりasciiで大きい適当な文字に更新する、といった操作をすることで求められます。

操作は N 回行うので O(N) 、各操作内にあるBIT上の二分探索、BITへの加算、セグメント木による区間最小値の取得、セグメント木の1点更新はすべて O(lgN) で行うことができるので、この問題は O(N lgN) で解くことができました。


コード

#include <bits/stdc++.h>
using namespace std;

struct BinaryIndexedTree {
  BinaryIndexedTree(int n) : n(n + 1), v(n + 2, 0) { init(); }

  vector<int> v;
  int n, r;

  void init() {
    r = 1;
    while (2 * r <= n)
      r *= 2;
  }

  int sum(int i) {
    ++i;
    int ret = 0;
    while (i) {
      ret += v[i];
      i -= i & -i;
    }
    return ret;
  }

  void add(int i, int x) {
    ++i;
    while (i <= n) {
      v[i] += x;
      i += i & -i;
    }
  }

  int lower_bound(int w) {
    int idx = 0;
    for (int k = r; k > 0; k /= 2) {
      if (idx + k <= n && v[idx + k] < w) {
        w -= v[idx + k];
        idx += k;
      }
    }
    return idx;
  }
};

struct segtree {
  segtree() {}
  segtree(int n, vector<char> v) : n(n) { init(v); }

  pair<char, int> id = make_pair('{', -1);
  int n;
  vector<pair<char, int>> node;

  void init(vector<char> v) {
    int n_ = n;
    n = 1;
    while (n < n_)
      n *= 2;

    node.assign(2 * n - 1, id);
    for (int i = 0; i < v.size(); ++i) {
      int idx = i + n - 1;
      node[idx] = make_pair(v[i], i);
    }
    for (int i = n - 2; i >= 0; --i) {
      node[i] = min(node[2 * i + 1], node[2 * i + 2]);
    }
  }

  pair<char, int> find(int a, int b, int k, int l, int r) {
    if (b <= l || r <= a)
      return id;
    if (a <= l && r <= b)
      return node[k];

    return min(find(a, b, 2 * k + 1, l, (l + r) / 2),
               find(a, b, 2 * k + 2, (l + r) / 2, r));
  }

  pair<char, int> find(int a, int b) { return find(a, b, 0, 0, n); }

  void update(int k) {
    k += n - 1;
    node[k] = id;
    while (k) {
      k = (k - 1) / 2;
      node[k] = min(node[2 * k + 1], node[2 * k + 2]);
    }
  }
};

int main() {
  string s;
  int k;

  cin >> s >> k;
  vector<char> v(s.size());
  for (int i = 0; i < s.size(); ++i)
    v[i] = s[i];

  BinaryIndexedTree bit(s.size());
  segtree seg(s.size(), v);

  for (int i = 0; i < s.size(); ++i)
    bit.add(i, 1);

  string ans;
  for (int i = 0; i < s.size(); ++i) {
    int r = bit.lower_bound(k + 1);
    pair<char, int> c = seg.find(0, r + 1);
    seg.update(c.second);
    bit.add(c.second, -1);
    k -= bit.sum(c.second);

    ans.push_back(c.first);
  }

  cout << ans << endl;
}

Road Improvement (道路網改修)

ジャッジ
Road Improvement | Aizu Online Judge

概要

N 頂点 M 辺の有向グラフが与えられます。このグラフにいくつかの有向辺を追加することで、任意の頂点からすべての辺を1度以上通ってもとの頂点に戻れるグラフを構成したいです。
最小でいくつの辺を追加しなくてはならないかを答えなさい。

解法

ほとんど考察だけの問題です。

強連結成分分解をして強連結成分ごとに考えると、強連結成分の定義より、強連結成分内の任意の辺を1度以上通ることができます。
よって、強連結成分分解してできたグラフについてのみ考えればよいことがわかります。
強連結成分分解後のグラフの出次数0のノードから別のノードに行くことができないことを考えると、このノードから新たに辺を生やさなくてはなりません。
また、入次数0のノードも、そのノード以外から開始すると辿れないことがわかるので、ここにも新たな辺が必要です。
出次数0のノード数をa、入次数0のノードをbとすると、数が多い方から一本ずつ数が小さい方に辺を繋げるのが最適だとわかるので、答えはmax(a, b)になります。

おちついて考えてみるとわかるかも

実装はほぼ強連結成分分解パートだけなので、考察さえすればあとは次数を数えるだけになりかなり楽に解けると思います。

コード

#include <bits/stdc++.h>
using namespace std;

struct StronglyConnectedComponents {
  int n;
  vector<vector<int>> oG, rG;
  vector<int> comp, order, used;
  vector<pair<int, int>> edges;

  StronglyConnectedComponents(int n)
      : n(n), oG(n), rG(n), comp(n, -1), used(n, 0) {}

  int operator[](int k) { return comp[k]; }

  void add_edge(int u, int v) {
    oG[u].push_back(v);
    rG[v].push_back(u);
    edges.emplace_back(u, v);
  }

  void dfs(int v) {
    if (used[v])
      return;
    used[v] = true;
    for (int to : oG[v])
      dfs(to);
    order.push_back(v);
  }

  void rdfs(int v, int k) {
    if (~comp[v])
      return;
    comp[v] = k;
    for (int to : rG[v])
      rdfs(to, k);
  }

  void build(vector<vector<int>> &t) {
    for (int i = 0; i < n; ++i)
      dfs(i);

    reverse(order.begin(), order.end());
    int k = 0;
    for (int i : order)
      if (comp[i] == -1)
        rdfs(i, k++);

    t.resize(k);
    set<pair<int, int>> connect;
    for (auto &e : edges) {
      int u = comp[e.first], v = comp[e.second];
      if (u == v || connect.count({u, v}))
        continue;
      t[u].push_back(v);
      connect.emplace(u, v);
    }
  }
};

bool a[10101], b[10101];

int main() {
  int n, m;
  cin >> n >> m;

  StronglyConnectedComponents G(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    G.add_edge(u, v);
  }

  vector<vector<int>> v;
  G.build(v);

  if (v.size() == 1) {
    cout << 0 << endl;
    return 0;
  }

  memset(a, true, sizeof(a));
  memset(b, true, sizeof(b));
  for (int i = 0; i < v.size(); ++i) {
    for (auto to : v[i]) {
      a[i] = false;
      b[to] = false;
    }
  }

  int acnt = 0, bcnt = 0;
  for (int i = 0; i < v.size(); ++i) {
    if (a[i])
      acnt++;
    if (b[i])
      bcnt++;
  }

  cout << max(acnt, bcnt) << endl;
}

Charging System for Network (ネットワークの課金システム)

ジャッジ
Charging System for Network | Aizu Online Judge

概要

N頂点の無向木が与えられる。
以下のクエリを処理してください。

  • ノード x につながっているすべての辺のコストを d 増加させる
  • ノード s, t 間の距離を出力する。ただし、コストがK の倍数であるような辺のコストは0であるものとする。

解法

気合で通したのであまり参考にしないで！！！(大声)

DEGwerさんにヒントをもらいつつ通しました、DEGwerさんありがとうございました(ありがとう……ありがとう……)

ノード x につながっているすべての辺のコストを愚直に増やしてしまうと、隣接行列でコストを管理してもクエリごとに O(N) かかってしまうので避けたい。
これは頂点 i (0 \leq i < N の周りにどれだけコストが追加されたかを配列にもっておき、そのノードを通った時にコストとして加算することで O(1) に抑える。

このままでは2つ目のクエリが処理できないので、クエリの平方分割を考える。
クエリ1つごとに現れるノードは高々2つなので、バケット1つにつき高々 2 \times \sqrt{Q} 個の頂点を見る必要があることがわかる。
このノードを使って木を縮約したいが、2頂点間の距離を求めるクエリが存在するため、使用することが決まった2頂点が合流する頂点も縮約後の頂点に含めるものとする。これを含めても高々 4 \times \sqrt{Q} 頂点(かな？)の木になる。
縮約後の頂点以外のノードの周りにコストが加算されることはないことを利用して、辺として潰されるノードの周りに加算されているコストは、縮約後の木の辺のコストとしてしまうと計算量に影響がなくて済む。
2つ目のクエリが与えられたら、縮約後の木をdfsなどして2点間の距離をO(\sqrt{Q})かけて探索することで求められます。

バケットごとに使う頂点の列挙はオイラーツアーや木DPなどをしてO(N)、その間の距離を求めるのも dfsなどで O(N)でできるので、木の縮約にO(N)
クエリ1つにつき O(1 + \sqrt{Q}) なので、全体で O(N \times \sqrt{Q}) で済む。


が、愚直に実装したらTL3secに対し5secちょっとかかったので、

  • vectorをできるだけ使わず固定長の配列に(これで0.4secくらい改善)
  • 複数回使う値で、前もって計算できる値を最初に計算(これで0.2secくらい改善)
  • これ以上思いつかなかったので関数の前に何も考えずinlineをつける(これで2secくらい改善(!!?))

などしてTL(3sec)ピッタリで通しました。

辺を見る一回一回で加算されいているコストの追加、 K の倍数かどうかの判定などをするので非常にバグりやすいです。
HL分解っぽいことをして高速に通している人がいるらしい(要出典)ので、その解法を参考にするほうがいいかも



コード

#include <bits/stdc++.h>
using namespace std;

const int inf = 1001001001;

struct e {
  int to, cost;
  e(int to, int cost) : to(to), cost(cost) {}
};

struct edge {
  int to;
  bool edge_type;
  long long cost, scost, tcost;

  edge() {}
  edge(int to, long long cost, bool edge_type, long long scost, long long tcost)
      : to(to), cost(cost), edge_type(edge_type), scost(scost), tcost(tcost) {}
};

struct query {
  bool type;
  int a, b;
  query() {}
  query(char s, int a, int b) : a(a), b(b) { type = (s == 'a'); }
};

int n, k, cnt;
vector<e> G[101010];
vector<edge> minG[101010];
query Q[1000];
int depth[101010], euler_tour[202020];
long long add[101010];
bool used[101010];

long long sqrt_int(long long n) {
  long long l = 1, r = n;
  while (r - l > 1) {
    long long m = (l + r) / 2;
    if (m * m <= n)
      l = m;
    else
      r = m;
  }
  return l;
}

inline void dfs(int v = 0, int p = -1, int d = 0) {
  euler_tour[cnt++] = v;
  depth[v] = d;
  for (auto u : G[v]) {
    if (u.to == p)
      continue;
    dfs(u.to, v, d + 1);
    euler_tour[cnt++] = v;
  }
}

inline void dfs2(int v, int from, int p = -1, long long cost = 0, int cnt = 0,
                 int scost = -1, int tcost = -1) {
  if (cnt == 0) {
    for (auto u : G[v]) {
      if (u.to == p)
        continue;
      dfs2(u.to, from, v, 0, cnt + 1, u.cost + add[u.to], u.cost + add[v]);
    }
  } else if (used[v]) {

    if (cnt == 1) {
      minG[v].push_back(edge(from, scost - add[v], true, -1, -1));
      minG[from].push_back(edge(v, scost - add[v], true, -1, -1));
    } else {
      minG[v].push_back(edge(from, cost, false, tcost, scost));
      minG[from].push_back(edge(v, cost, false, scost, tcost));
    }

    dfs2(v, v, p, 0, 0, -1, -1);
  } else {
    for (auto u : G[v]) {
      if (u.to == p)
        continue;

      long long edge_cost = add[v] + add[u.to] + u.cost;
      if (used[u.to] || edge_cost % k == 0)
        edge_cost = 0;
      dfs2(u.to, from, v, cost + edge_cost, cnt + 1, scost, u.cost + add[v]);
    }
  }
}

inline bool dfs3(int s, int to, int p = -1, long long cost = 0) {
  if (s == to) {
    printf("%d\n", cost);
    return true;
  }

  for (auto u : minG[s]) {
    int t = u.to;
    if (t == p)
      continue;

    if (u.edge_type) {
      long long edge_cost = u.cost + add[s] + add[t];
      if (edge_cost % k == 0)
        edge_cost = 0;
      if (dfs3(t, to, s, cost + edge_cost))
        return true;
    } else {
      long long scost = u.scost + add[s], tcost = u.tcost + add[t];
      if (scost % k == 0)
        scost = 0;
      if (tcost % k == 0)
        tcost = 0;
      if (dfs3(t, to, s, cost + u.cost + scost + tcost))
        return true;
    }
  }
  return false;
}

int main() {
  scanf("%d %d", &n, &k);

  for (int i = 0; i < n - 1; ++i) {
    int u, v, c;
    scanf("%d %d %d", &u, &v, &c);

    G[u].push_back(e(v, c));
    G[v].push_back(e(u, c));
  }

  dfs();

  int q;
  scanf("%d", &q);

  int root_q = sqrt_int(q);
  int r = (q + root_q - 1) / root_q;
  for (int p = 0; p < r; ++p) {
    int rr = min(root_q, q - p * root_q);
    memset(used, false, sizeof(used));
    for (int i = 0; i < n; ++i)
      minG[i].clear();

    for (int i = 0; i < rr; ++i) {
      char s[10];
      int a, b;
      scanf("%s %d %d", s, &a, &b);
      Q[i] = query(s[0], a, b);

      if (Q[i].type) {
        used[a] = true;
      } else {
        used[a] = used[b] = true;
      }
    }

    pair<int, int> mini, root;
    mini = root = make_pair(inf, -1);
    for (int i = 0; i < cnt; ++i) {
      int v = euler_tour[i];
      mini = min(mini, make_pair(depth[v], v));
      if (used[v]) {
        if (mini.second != -1)
          used[mini.second] = true;
        mini = make_pair(depth[v], v);
        root = min(root, make_pair(depth[v], v));
      }
    }

    dfs2(root.second, root.second);

    for (int i = 0; i < rr; ++i) {
      if (Q[i].type) {
        add[Q[i].a] += Q[i].b;
      } else {
        dfs3(Q[i].a, Q[i].b);
      }
    }
  }
}

*1: [l, r) は、 (l ≦ i < r) であるような任意の i を指します

*2:gcdは最大公約数のこと

*3:0-indexed