[NAPC R1] rStage5 Solution

· · 题解

rStage5 - Hard Conveyors

预计难度：*2100 左右，绿\~蓝。

前置芝士：lca，树剖（其实也可以不用）。

设 dis_u 为离 u 点最近的一个关键点与它的距离，显然可以使用 dijkstra 等算法 O(n\log n) 求出（以堆优化 dijkstra 为例：将所有关键节点的 dis 设为 0 并全部加入优先队列，然后跑正常的堆优化 dijkstra 即可）。

（upd：好像可以 dfs 就能预处理出这个 dis 数组，但是好像挺麻烦，没试过。）

因为每条路径显然形如 s\to x\to \operatorname{key}(x)\to x\to t，其中 x 是 s\to t 路径上的点（可以取到端点），\operatorname{key}(x) 是离 x 最近的关键点。那么预处理出 dis 数组，对于每次询问 O(n) 枚举 s\to t 上的 x 统计这种情况下的最小路径长度，总复杂度 O(n\log n+qn)。

发现枚举 x 实际上只是为了求 dis_x 的最小值（因为 s\to x 加上 x\to t 的长度一定等于 s\to t）。于是直接套个树剖求一条路径上的 dis 最小值即可，复杂度 O(n\log n+q\log n)。

upd：好像倍增求 lca 也可以维护一条路径上的最小值 qwq：设 st_{i,j} 为 i 到根的链中底部 2^j 个点的 dis 最小值（即集合 \complement_{i\to fa_{i,j}}\{fa_{i,j}\} 内 dis 的最小值，其中 fa_{i,j} 表示 i 点的 2^j 级祖先，u\to v 表示 u 到 v 的最短路径上的点构成的集合）。那么求 lca 时 u,v 两个点往上跳的同时用 st 数组更新 dis 最小值就行了。This sol code。

code：

int n, q, k;
int head[N], ne[N << 1], to[N << 1], w[N << 1], idx1 = 0;
void add(int u, int v, int x) {
    to[idx1] = v, w[idx1] = x, ne[idx1] = head[u], head[u] = idx1++;
}
int dis[N];
bool dijvis[N];
void dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    memset(dijvis, 0, sizeof dijvis);
    priority_queue<pii, vector<pii>, greater<pii>> Q;
    while(k--) {
        int x = read();
        Q.em(dis[x] = 0, x);
    }
    while(!Q.empty()) {
        int u = Q.top().y; Q.pop();
        if(dijvis[u]) continue;
        dijvis[u] = 1;
        for(int i = head[u]; ~i; i = ne[i]) {
            int &v = to[i];
            if(dis[v] > dis[u] + w[i])
                dis[v] = dis[u] + w[i], Q.em(dis[v], v);
        }
    }
}
#define ws ambiguous1
int ws[N];
int siz[N], fa[N], son[N], dph[N], top[N], dfn[N], rnk[N];
void dfs1(int u, int f) {
    dph[u] = dph[f] + 1, fa[u] = f, siz[u] = 1;
    for(int i = head[u]; ~i; i = ne[i]) if(to[i] != f) {
        int &v = to[i];
        ws[v] = ws[u] + w[i];
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
int timer = 0;
void dfs2(int u, int tp) {
    top[u] = tp, dfn[u] = ++timer, rnk[timer] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int i = head[u]; ~i; i = ne[i]) if(to[i] != fa[u] && to[i] != son[u]) {
        int &v = to[i];
        dfs2(v, v);
    }
}
int st[20][N];
int minimum(int l, int r) {
    if(l > r) return 0x3f3f3f3f;
    int k_ = __lg(r - l + 1);
    return min(st[k_][l], st[k_][r - (1 << /*k*/k_) + 1]);
}
int get_ans(int u, int v) {
    int res = 0x3f3f3f3f, tmp = ws[u] + ws[v];
    while(top[u] != top[v]) {
        if(dph[top[u]] < dph[top[v]]) swap(u, v);
        res = min(res, minimum(dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    if(dph[u] > dph[v]) swap(u, v);
    res = min(res, minimum(dfn[u], dfn[v]));
    return tmp - (ws[u] << 1) + (res << 1);
    //tmp - ws[lca] * 2 = u->v 路径长度
}
bool major(int Testcase = 1) {
    memset(head, -1, sizeof head);
    n = read(), q = read(), k = read();
    for(int i = 1; i < n; i++) {
        int u = read(), v = read(), ww = read();
        add(u, v, ww), add(v, u, ww);
    }
    dijkstra();
    dfs1(1, 0);
    dfs2(1, 0);
    memset(st, 0x3f, sizeof st);
    for(int i = 1; i <= n; i++) st[0][i] = dis[rnk[i]];
    for(int j = 1; j < 20; j++) for(int i = 1; i <= n; i++)
        if(i + (1 << j) - 1 <= n)
            st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    while(q--) {
        int s = read(), t = read();
        printf("%d\n", get_ans(s, t));
    }
    return Testcase;
}