https://smijake3.hatenablog.com/entry/2019/02/27/231503

コンテスト中は(E問題でハマってて)見なかった問題。後日公式の解説見ながら通した。

問題概要

1からNまでの番号が付いた ${N}$ 個の頂点を持つ木がある。

この木の上を1からMまでの番号がついた ${M}$ 人の人が移動し、 ${i}$ 番目の人は頂点 ${V_i}$ からちょうど ${L_i}$ 回辺を伝って頂点を移動する。
この時、 ${x}$ 番目の辺を通ると ${C_x}$ 点得られる。

各人 ${i}$ について、 ${L_i}$ 回の移動で得られる最大の点数を求めよ。

制約

${2 \le N \le 10^5}$
${1 \le M \le 10^5}$
${1 \le C_i \le 10^9}$
${1 \le L_i \le 10^9}$

解法

重心分解 + Convex Hull Trick で解ける。

まず、人 ${i}$ が最大得点となる移動方法として、頂点 ${V_i}$ から点数が大きい辺まで移動して往復し続けるのがよさそうだと分かる。

f:id:smijake3:20190227004933p:plain

ここで、往復する辺の点数を ${A}$ 、往復する辺まで到達するまでに得られる点数の総和を ${B}$ 、往復するまでに移動する回数を ${D}$ とすると、得られる総得点は
${A(L_i - D) + B = A L_i + B - A D}$
となる。
そのため、単純な解法としては、各辺 ${e}$ についてこの点数を計算し、最大となる時の点数を解とすればよい。

しかし、この計算を ${M}$ 回行うと ${O(NM)}$ となるため間に合わない。
そのため、重心分解を使って工夫して解く。

まず重心分解を行う。その上で、分解した各部分木上で計算を行う。

ある部分木に頂点 ${V_i}$ が含まれるとする。この部分木では、人 ${i}$ が頂点 ${V_i}$ から、重心となる頂点 ${v}$ を経由し、部分木上を移動する場合の最大得点を求める。
(頂点 ${v}$ を経由しない場合の最大得点は、この木を重心で更に分解した部分木で計算する)

また、ここでは人 ${i}$ が移動回数的に頂点 ${v}$ に到達できるとする。(到達できない場合はここでは計算しない)

f:id:smijake3:20190227005616p:plain

頂点 ${v}$ を開始地点とし、 ${x}$ 回の移動で辺 ${e}$ を往復する場合の得点は、辺 ${e}$ の点数を ${A_e}$ 、辺 ${e}$ の到達までに得られる点数の総和を ${B_e}$ 、辺 ${e}$ 到達までの移動回数を ${D_e}$ とすると、総得点は ${A_e x + B_e - A_e D_e}$ となる。

ここで
${f_e(x) = \left\{ \begin{array}{ll} A_e x + B_e - A_e D_e & (x \ge D_e) \\ 0 & (x < D_e) \end{array} \right.}$
と定義する。
この時、人 ${i}$ が頂点 ${v}$ を経由した場合の最大得点は、 ${V_i}$ から ${v}$ まで移動する回数を ${K_i}$ 、その間に得られる点数を ${W_i}$ とした時、
$W_i + \max_e f_e(L_i - K_i)$
として計算できる。

各iについての $\max_e f_e(L_i - K_i)$ はConvex Hull Trickで計算する。
直線 ${f_e}$ を追加していって、計算が必要な各 ${x = L_i - K_i}$ について最大値を計算すればよい。

この部分木における計算量は、含む頂点数を ${n}$ 、含む人の数を ${m}$ とすると ${O(n \log n + m)}$ となるため、全体の計算量は ${O((N \log N + M) \log N)}$ となる。

実装

Convex Hull Trickで計算を行う際、求める座標サイズに合わせてメモリを動的に確保するLi Chao Treeを使って実装してある。

提出コード (C++14): Submission #4352791 - 全国統一プログラミング王決定戦本戦

#define LV 19
#define N 100005
 
int n;
vector<int> g[N];
 
// ===== ここから重心分解
int root;
vector<int> g0[N];
int parent[N], level[N];
 
bool c_used[N];
int sz[N];
int count_dfs(int v, int p) {
  int c = 1;
  repe(w, g[v]) {
    if(w == p || c_used[w]) continue;
    c += count_dfs(w, v);
  }
  return sz[v] = c;
}
 
int search_centroid(int v, int p, int s) {
  if((s - sz[v])*2 > s) {
    return -1;
  }
  bool ok = true;
  repe(w, g[v]) {
    if(w == p || c_used[w]) continue;
 
    int x = search_centroid(w, v, s);
    if(x != -1) {
      return x;
    }
    if(sz[w]*2 > s) {
      ok = false;
      break;
    }
  }
  return ok ? v : -1;
}
 
vector<P> gt[N];
 
void centroid() {
  queue<int> que;
 
  int s = count_dfs(0, -1);
  int x = search_centroid(0, -1, s);
  que.push(x);
  c_used[x] = true;
  root = x;
  parent[x] = -1;
  level[x] = 0;
 
  while(!que.empty()) {
    int v = que.front(); que.pop();
    repe(w, g[v]) {
      if(c_used[w]) {
        continue;
      }
 
      int s = count_dfs(w, -1);
      int x = search_centroid(w, -1, s);
      g0[v].push_back(x);
      parent[x] = v;
      level[x] = level[v] + 1;
 
      que.push(x);
      c_used[x] = true;
    }
  }
}
// ===== ここまで重心分解

// ===== Li Chao (Segment) Tree 
class LiChaoTree {
  int n;
  ll *xs, *p, *q;
  bool *u;
 
  void _add_line(ll a, ll b, int k, int l, int r) {
    while(r-l > 0) {
      int m = (l + r) >> 1;
      if(!u[k]) {
        p[k] = a; q[k] = b;
        u[k] = true;
        return;
      }
 
      ll lx = xs[l], mx = xs[m], rx = xs[r-1];
      ll pk = p[k], qk = q[k];
      bool left = (a*lx+b < pk*lx+qk);
      bool mid = (a*mx+b < pk*mx+qk);
      bool right = (a*rx+b < pk*rx+qk);
      if(left && right) {
        p[k] = a; q[k] = b;
        return;
      }
      if(!left && !right) {
        return;
      }
      if(mid) {
        swap(p[k], a);
        swap(q[k], b);
      }
      if(left != mid) {
        k = 2*k+1; r = m;
      } else {
        k = 2*k+2; l = m;
      }
    }
  }
 
  ll _query(int k, ll x) {
    k += n - 1;
    ll s = u[k] ? p[k]*x+q[k] : INFLL;
    while(k > 0) {
      k = (k - 1) / 2;
      if(u[k]) {
        ll r = p[k]*x+q[k];
        s = min(s, r);
      }
    }
    return s;
  }
 
public:
  LiChaoTree(const vector<int> &ps) {
    int n0 = ps.size();
    n = 1;
    while(n < n0) n <<= 1;
 
    xs = new ll[2*n];
    p = new ll[2*n];
    q = new ll[2*n];
    u = new bool[2*n];
 
    rep(i, 2*n) u[i] = false;
    rep(i, n0) xs[i] = ps[i];
    repl(i, n0, n-1) xs[i] = INF;
  }
  ~LiChaoTree() {
    delete xs;
    delete p;
    delete q;
    delete u;
  }
 
  void add_line(ll a, ll b) {
    _add_line(a, b, 0, 0, n);
  }
 
  void add_segment_line(ll a, ll b, int l, int r) {
    if(r == -1) r = n;
    ll l0 = l + n, r0 = r + n;
    ll s0 = l, t0 = r, sz = 1;
    while(l0 < r0) {
      if(r0 & 1) {
        --r0; t0 -= sz;
        _add_line(a, b, r0-1, t0, t0+sz);
      }
      if(l0 & 1) {
        _add_line(a, b, l0-1, s0, s0+sz);
        ++l0; s0 += sz;
      }
      l0 >>= 1; r0 >>= 1;
      sz <<= 1;
    }
  }
 
  // xs[i]の最小値を求める
  ll query(int i) {
    return _query(i, xs[i]);
  }
};

// ===== 座標圧縮
map<int, int> compress(const vector<int> &xs) {
  map<int, int> result;
  for(int i=0; i<xs.size(); ++i) {
    result[xs[i]] = 0;
  }
  int i = 0;
  for(auto it = result.begin(); it != result.end(); ++it, ++i) {
    result[(*it).first] = i;
  }
  return result;
}

// この関数内で解を計算する
// 各levelにおける、その頂点が含まれる部分木の重心頂点からの移動回数(dist)とその間の総得点(cost)
ll cost[LV][N], dist[LV][N];

ll vs[N], ls[N]; // vs[i] = V_i, ls[i] = L_i
vector<int> vv[N]; // vv[u]: 頂点uが始点となる人の番号リスト
ll res[N]; // res[i]: 人iの最大得点
int used[N]; // used: 各頂点の探索済みフラグ
void solve() {
  // まず重心分解する
  centroid();

  // 頂点uが重心となる部分木について計算する
  rep(u, n) {
    vector<int> qs; // この部分木に含まれる人iのリスト
    set<int> ss; // Convex Hull Trickで計算が必要となる座標
    vector<int> ws; // BFSでの辿り順
 
    queue<int> que;
    int lv = level[u];
    que.push(u);
    cost[lv][u] = dist[lv][u] = 0;
    used[u] = u+1;
    ws.push_back(u);
 
    repe(i, vv[u]) {
      qs.push_back(i);
      ss.insert(ls[i]);
    }
 
    // BFSでこの部分木に含まれる頂点を辿る
    while(!que.empty()) {
      int v = que.front(); que.pop();
      ll dv = dist[lv][v], cv = cost[lv][v];
      repe(&p, gt[v]) {
        int w = p.first, c = p.second;
        if(level[w] < lv || used[w] == u+1) {
          continue;
        }
        cost[lv][w] = cv + c;
        dist[lv][w] = dv + 1;
        que.push(w);
        ws.push_back(w);
        used[w] = u+1;
 
        repe(i, vv[w]) {
          if(ls[i] - dist[lv][w] >= 0) {
            qs.push_back(i);
            ss.insert(ls[i] - dist[lv][w]);
          }
        }
      }
    }
    // 座標を整理 (座標圧縮もする)
    vector<int> xs;
    repe(x, ss) xs.push_back(x);
    map<int, int> comp = compress(xs);
    LiChaoTree lct(xs);
 
    // 直線を追加しながら、計算が必要となる各座標xについて
    // \max_e f_e(x) の値を求める
    vector<ll> rs;
    int cur = 0;
    rep(i, ws.size()) {
      ll w = ws[i], c = 0;
      ll d = dist[lv][w];
      while(cur < xs.size() && xs[cur] < d) {
        rs.push_back(lct.query(cur++));
      }
      repe(&p, gt[w]) {
        c = max(c, (ll)p.second);
      }
      lct.add_line(-c, -(cost[lv][w] - c*d));
    }
    while(cur < xs.size()) {
      rs.push_back(lct.query(cur++));
    }
 
    // 各人iについて、最大得点を求める
    repe(i, qs) {
      ll x = ls[i] - dist[lv][vs[i]];
      ll r0 = cost[lv][vs[i]] - rs[comp[x]];
      res[i] = max(res[i], r0);
    }
  }
}
 
int main() {
  scanf("%d", &n);
  rep(i, n-1) {
    int a, b, c; scanf("%d %d %d", &a, &b, &c); --a; --b;
    // こっちは重心分解で使うデータ
    g[a].push_back(b);
    g[b].push_back(a);
 
    // こっちは solve() 内で使うデータ
    gt[a].push_back(P(b, c));
    gt[b].push_back(P(a, c));
  }
  int m;
  scanf("%d", &m);
  rep(i, m) {
    scanf("%lld %lld", vs+i, ls+i); --vs[i];
    vv[vs[i]].push_back(i);
  }
  solve();
  rep(i, m) {
    printf("%lld\n", res[i]);
  }
  return 0;
}