简答题
偏难
#22097
数据传输(transmit)
数据传输(transmit)



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 200500, B = 20, K = 3;
ll n, q, T;
ll v[N], mn[N];
vector<ll> e[N];
ll f[B][N], dep[N];
ll dis[B][N][K][K];
void gi(ll &x, ll y) {
x = min(x, y);
}
void dfs(ll k, ll fa) {
dep[k] = dep[fa] + 1;
f[0][k] = fa;
for (ll i = 1; i < B; i++) {
f[i][k] = f[i - 1][f[i - 1][k]];
}
auto D = dis[0][k];
if (T == 1) {
D[0][0] = v[fa];
}
if (T == 2) {
D[0][0] = D[1][0] = v[fa];
D[0][1] = 0;
}
if (T == 3) {
D[0][0] = D[1][0] = D[2][0] = v[fa];
D[0][1] = D[1][2] = 0;
D[2][2] = mn[k];
}
for (ll i = 1; i < B; i++) {
for (ll x = 0; x < 3; x++) {
for (ll y = 0; y < 3; y++) {
for (ll z = 0; z < 3; z++) {
gi(dis[i][k][x][z], dis[i - 1][k][x][y] + dis[i - 1][f[i - 1][k]][y][z]);
}
}
}
}
for (auto to : e[k]) {
if (to != fa) {
dfs(to, k);
}
}
}
ll lca(ll x, ll y) {
if (dep[x] < dep[y]) {
swap(x, y);
}
for (ll i = B - 1; i >= 0; i--) {
if (dep[f[i][x]] >= dep[y]) {
x = f[i][x];
}
}
if (x == y) {
return x;
}
for (ll i = B - 1; i >= 0; i--) {
if (f[i][x] != f[i][y]) {
x = f[i][x];
y = f[i][y];
}
}
return f[0][x];
}
vector<ll> calc(ll k, ll l) {
vector<ll> res(3, v[k]);
for (ll i = B - 1; i >= 0; i--) {
if (dep[f[i][k]] < dep[l]) {
continue;
}
vector<ll> nw = res;
fill(res.begin(), res.end(), 1e18);
for (ll x = 0; x < 3; x++) {
for (ll y = 0; y < 3; y++) {
gi(res[y], nw[x] + dis[i][k][x][y]);
}
}
k = f[i][k];
}
return res;
}
ll calcdis(ll x, ll y) {
ll l = lca(x, y);
auto F = calc(x, l), G = calc(y, l);
ll res = 1e18;
gi(res, F[0] + G[0] - v[l]);
for (ll i = 0; i < T; i++) {
for (ll j = 0; j < T; j++) {
gi(res, F[i] + G[j] + (mn[l] * (i + j > T)));
}
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> q >> T;
for (ll i = 1; i <= n; i++) {
cin >> v[i];
mn[i] = v[i];
}
for (ll i = 1; i < n; i++) {
ll x, y;
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
mn[x] = min(mn[x], v[y]);
mn[y] = min(mn[y], v[x]);
}
memset(dis, 1, sizeof(dis));
dfs(1, 0);
while (q--) {
ll s, t;
cin >> s >> t;
cout << calcdis(s, t) << '\n';
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。