AtCoder: 全国統一プログラミング王決定戦本戦 - G問題: Greatest Journey
コンテスト中は(E問題でハマってて)見なかった問題。後日公式の解説見ながら通した。
問題概要
1からNまでの番号が付いた個の頂点を持つ木がある。
この木の上を1からMまでの番号がついた人の人が移動し、番目の人は頂点からちょうど回辺を伝って頂点を移動する。
この時、番目の辺を通ると点得られる。
各人について、回の移動で得られる最大の点数を求めよ。
制約
解法
重心分解 + Convex Hull Trick で解ける。
まず、人が最大得点となる移動方法として、頂点から点数が大きい辺まで移動して往復し続けるのがよさそうだと分かる。
ここで、往復する辺の点数を、往復する辺まで到達するまでに得られる点数の総和を、往復するまでに移動する回数をとすると、得られる総得点は
となる。
そのため、単純な解法としては、各辺についてこの点数を計算し、最大となる時の点数を解とすればよい。
しかし、この計算を回行うととなるため間に合わない。
そのため、重心分解を使って工夫して解く。
まず重心分解を行う。その上で、分解した各部分木上で計算を行う。
ある部分木に頂点が含まれるとする。この部分木では、人が頂点から、重心となる頂点を経由し、部分木上を移動する場合の最大得点を求める。
(頂点を経由しない場合の最大得点は、この木を重心で更に分解した部分木で計算する)
また、ここでは人が移動回数的に頂点に到達できるとする。(到達できない場合はここでは計算しない)
頂点を開始地点とし、回の移動で辺を往復する場合の得点は、辺の点数を、辺の到達までに得られる点数の総和を、辺到達までの移動回数をとすると、総得点は となる。
ここで
と定義する。
この時、人が頂点を経由した場合の最大得点は、からまで移動する回数を、その間に得られる点数をとした時、
として計算できる。
各iについての はConvex Hull Trickで計算する。
直線 を追加していって、計算が必要な各 について最大値を計算すればよい。
この部分木における計算量は、含む頂点数を、含む人の数をとすると となるため、全体の計算量は となる。
実装
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; }