一道练习点分治的题。

对于每一个点进行一遍 Dijkstra 是不可接受的，考虑点分治处理。

我们按照点分治的方式递归处理一个询问，假设当前递归到的分治中心是 $c$，询问的两点是 $u,v$，那么我们就要为最短路径分类。所有的最短路径可以分为三类：

  • $\text{(A).}$ $z$ 的最短路经过 $c$。以分治中心 $c$ 为起点跑 Dijkstra，计算到 $c$ 到分治连通块内所有节点的最短路，那么此时 $d(u,v)=d(c,u)+d(c,v)$。
  • $\text{(B).}$ $u,v$ 在分治连通块的不同子树内且最短路不经过 $c$。这是最短路必定经过外环边，若子树个数为 $s$，外环边最多有 $s$ 条，对于每一条边，我们任取其一端点 $p$ ，计算 $p$ 到分治连通块内所有节点的最短路，那么此时有

$$ d(u,v)=\min_{i=1}^{s}\left(d(p_i,u)+d(p_i,v)\right) $$

  • $\text{(C).}$ $u,v$ 在分治连通块的同一子树内且最短路不经过 $c$。若最短路经过外环边，问题 $\text{(B)}$ 就可以解决。否则我们对这个子树进行递归分治处理。

但是时间瓶颈是由子树个数 $s$ 决定的，因为我们对每一个分治重心都要跑 $s+1$ 遍 Dijkstra。根据题目条件，容易想到对整棵树进行三度化。此时对每一个分治重心只需最多跑 $4$ 遍 Dijkstra，而三度化最多只会新增 $n$ 个节点，所以总结点数仍是 $O(n)$ 的。

实际上分治时可以将所有询问离散化，在每次分治时一并处理，可以省很多空间。在递归时如果某个子树没有询问了，就不要向下递归，这样剪枝可以节省很多时间。

时间复杂度 $O(n\log^2n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
const int inf = 0x3f3f3f3f3f3f3f3fll;
int n, k, Q, m;
vector<pair<int, int>> G[200010];
vector<int> T[200010], outp;
int w[100010];
struct Q {
    int u, v;
} q[250010];
void trans() {
    m = n;
    queue<int> q; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        while (T[u].size() > 2) {
            int x = T[u].back(); T[u].pop_back();
            int y = T[u].back(); T[u].pop_back();
            int dx = G[u].back().second; G[u].pop_back();
            int dy = G[u].back().second; G[u].pop_back();
            m++;
            T[m].push_back(x), T[m].push_back(y);
            G[m].push_back({x, dx}), G[m].push_back({y, dy});
            T[u].push_back(m); G[u].push_back({m, 0});
        }
        for (int v : T[u]) q.push(v);
    }
    vector<tuple<int, int, int>> t;
    for (int u = 1; u <= m; u++)
        for (auto &[v, d] : G[u]) t.push_back({u, v, d});
    for (auto &[u, v, d] : t) T[v].push_back(u), G[v].push_back({u, d}); 
}
vector<int> all, todo;
bool vis[200010];
int siz[200010], bid[200010];
int dis[200010];
int ans[250010];
void getsz(int u, int fa) {
    siz[u] = 1; all.push_back(u);
    for (int v : T[u]) {
        if (v == fa || vis[v]) continue;
        getsz(v, u);
        siz[u] += siz[v];
    }
}
int getrt(int u, int fa, int sz) {
    for (int v : T[u]) {
        if (v == fa || vis[v]) continue;
        if (siz[v] > sz / 2) return getrt(v, u, sz);
    }
    return u;
}
void fill(int u, int fa, int id) {
    bid[u] = id;
    for (int v : T[u]) {
        if (v == fa || vis[v]) continue;
        fill(v, u, id);
    }
}
void dij(int s, vector<int> &em) {
    for (int u : em) dis[u] = inf;
    priority_queue<pair<int, int>> pq;
    dis[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        d = -d;
        for (auto [v, ds] : G[u]) {
            if (!bid[v] || d + ds >= dis[v]) continue;
            dis[v] = d + ds;
            pq.push({-dis[v], v});   
        }
    }
}
void find(int u, int fa) {
    for (auto [v, ds] : G[u])
        if (bid[u] > 0 && bid[v] > 0 && bid[u] < bid[v]) todo.push_back(u);
    for (int v : T[u]) {
        if (v == fa || vis[v]) continue;
        find(v, u);
    }
}
void work(int u, vector<int> &que) {
    getsz(u, 0);
    int rt = getrt(u, 0, siz[u]);
    vis[rt] = 1;
    int tid = 0;
    int pson[4] = {0, 0, 0, 0};
    bid[rt] = -1;
    for (int son : T[rt]) {
        if (vis[son]) continue;
        fill(son, rt, ++tid);
        pson[tid] = son;
    }
    for (int son : T[rt]) {
        if (vis[son]) continue;
        find(son, rt);
    }
    todo.push_back(rt);
    for (int now : todo) {
        dij(now, all);
        for (int id : que) {
            int qu = q[id].u, qv = q[id].v;
            ans[id] = min(ans[id], dis[qu] + dis[qv]);
        }
    }
    vector<int> subq[4];
    for (int id : que) {
        int qu = q[id].u, qv = q[id].v;
        if (bid[qu] == bid[qv]) subq[bid[qu]].push_back(id);
    }
    for (int u : all) bid[u] = 0;
    all.clear(); todo.clear();
    for (int i = 1; i <= tid; i++) 
        if (!subq[i].empty()) work(pson[i], subq[i]);
}
void solve() {
    n = read();
    for (int i = 2; i <= n; i++) {
        int p = read(), d = read();
        G[p].push_back({i, d});
        T[p].push_back(i);
    }
    for (int i = 1; i <= n; i++) if (T[i].empty()) k++, outp.push_back(i);
    for (int i = 1; i <= k; i++) w[i] = read();
    Q = read();
    for (int i = 1; i <= Q; i++) q[i].u = read(), q[i].v = read();
    trans();
    for (int i = 0; i < k; i++) {
        int u = outp[i], v = outp[(i + 1) % k];
        G[u].push_back({v, w[i + 1]});
        G[v].push_back({u, w[i + 1]});
    }
    for (int i = 1; i <= Q; i++) ans[i] = inf;
    vector<int> que;
    for (int i = 1; i <= Q; i++) que.push_back(i);
    work(1, que);
    for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
}