日経 G Greatest Journey
An optimal move is like this.
Fix the start vertex r. The red route is better than the orange one.
In general, if the maximum weight of the edges on the r-v path is greater than the weight of the edge between v and parent(v), then v is unnecessary. Maybe, some nodes are unreachable from the root within L steps. The red route is luckily better than the blue route but the blue route is impossible. It is not a coincidence. Actually we do not need to consider such a thing.
The remaining parts are really CodeChef. We just use the convex hull trick and the centroid decomposition.
Gaiseki ga 64bit seisu ni osamaranai node kiwotukete.
#include <stdio.h> #include <vector> #include <algorithm> using namespace std; typedef __int128_t i128; struct point { long long x, y; point(long long x_ = 0, long long y_ = 0) : x(x_), y(y_) {} }; point operator-(point a, point b) { a.x -= b.x; a.y -= b.y; return a; } i128 cross(point a, point b) { return (i128)a.x * b.y - (i128)a.y * b.x; } point H[100000]; int F, R; long long f(int k, long long x) { return H[k].x * x + H[k].y; } void push(long long x, long long y) { point p(x, y); while (R - F >= 2 && cross(H[R - 1] - H[R - 2], p - H[R - 1]) >= 0) R--; H[R++] = p; } long long zuida(long long x) { while (F + 1 < R && f(F, x) <= f(F + 1, x)) F++; return f(F, x); } struct edge { int v, w; }; int N, M; vector<edge> G[100000]; vector<int> Q[100000]; int V[100000]; int L[100000]; bool used[100000]; int S[100000]; long long ans[100000]; int E[100000]; long long U[100000]; long long D[100000]; long long X[100000]; long long max(long long x, long long y) { return x > y ? x : y; } void to(long long *x, long long y) { if (*x < y) *x = y; } struct foo { int s; long long d; long long m; }; void dfs2(int u, int p) { S[u] = 1; for (edge e : G[u]) if (e.v != p && !used[e.v]) { dfs2(e.v, u); S[u] += S[e.v]; } } int dfs3(int u, int p, int n) { for (edge e : G[u]) if (e.v != p && !used[e.v] && S[e.v] >= n / 2) { return dfs3(e.v, u, n); } return u; } void dfs4(int u, int p, vector<int> &c, vector<int> &q) { for (int i : Q[u]) q.push_back(i); c.push_back(u); for (edge e : G[u]) if (e.v != p && !used[e.v]) { E[e.v] = E[u] + 1; D[e.v] = D[u] + e.w; U[e.v] = e.w; X[e.v] = max(X[u], e.w); dfs4(e.v, u, c, q); } } void dfs(int u) { dfs2(u, -1); u = dfs3(u, -1, S[u]); used[u] = true; int m = G[u].size(); vector<int> cs, qs; E[u] = 0; D[u] = 0; U[u] = 0; X[u] = 0; dfs4(u, -1, cs, qs); auto it = remove_if(cs.begin(), cs.end(), [&](int i) { return X[i] > U[i]; }); cs.erase(it, cs.end()); sort(cs.begin(), cs.end(), [&](int i, int j) { if (U[i] != U[j]) return U[i] < U[j]; return D[i] - U[i] * E[i] < D[j] - U[j] * E[j]; }); sort(qs.begin(), qs.end(), [&](int i, int j) { return L[i] - E[V[i]] < L[j] - E[V[j]]; }); F = R = 0; for (int v : cs) push(U[v], D[v] - U[v] * E[v]); for (int i : qs) { if (L[i] >= E[V[i]]) { to(&ans[i], D[V[i]] + zuida(L[i] - E[V[i]])); } } for (edge e : G[u]) if (!used[e.v]) { dfs(e.v); } } int main() { scanf("%d", &N); for (int i = 0; i < N - 1; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); u--; v--; G[u].push_back({v, w}); G[v].push_back({u, w}); } scanf("%d", &M); for (int i = 0; i < M; i++) { scanf("%d %d", &V[i], &L[i]); V[i]--; Q[V[i]].push_back(i); } dfs(0); for (int i = 0; i < M; i++) { printf("%lld\n", ans[i]); } return 0; }