日経 G Greatest Journey


An optimal move is like this.

f:id:pekempey:20190218110709p:plain

Fix the start vertex r. The red route is better than the orange one.

f:id:pekempey:20190218111410p:plain

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;
}