简答题 偏难
#22097

数据传输(transmit)

数据传输(transmit)


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; #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&lt;ll&gt; e[N]; ll f[B][N], dep[N]; ll dis[B][N][K][K]; void gi(ll &amp;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 &lt; 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 &lt; B; i++) {         for (ll x = 0; x &lt; 3; x++) {             for (ll y = 0; y &lt; 3; y++) {                 for (ll z = 0; z &lt; 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] &lt; dep[y]) {         swap(x, y);     }          for (ll i = B - 1; i &gt;= 0; i--) {         if (dep[f[i][x]] &gt;= dep[y]) {             x = f[i][x];         }     }          if (x == y) {         return x;     }          for (ll i = B - 1; i &gt;= 0; i--) {         if (f[i][x] != f[i][y]) {             x = f[i][x];             y = f[i][y];         }     }          return f[0][x]; } vector&lt;ll&gt; calc(ll k, ll l) {     vector&lt;ll&gt; res(3, v[k]);          for (ll i = B - 1; i &gt;= 0; i--) {         if (dep[f[i][k]] &lt; dep[l]) {             continue;         }                  vector&lt;ll&gt; nw = res;         fill(res.begin(), res.end(), 1e18);                  for (ll x = 0; x &lt; 3; x++) {             for (ll y = 0; y &lt; 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 &lt; T; i++) {         for (ll j = 0; j &lt; T; j++) {             gi(res, F[i] + G[j] + (mn[l] * (i + j &gt; T)));         }     }          return res; } int main() {     ios::sync_with_stdio(0);     cin &gt;&gt; n &gt;&gt; q &gt;&gt; T;          for (ll i = 1; i &lt;= n; i++) {         cin &gt;&gt; v[i];         mn[i] = v[i];     }          for (ll i = 1; i &lt; n; i++) {         ll x, y;         cin &gt;&gt; x &gt;&gt; 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 &gt;&gt; s &gt;&gt; t;         cout &lt;&lt; calcdis(s, t) &lt;&lt; '\n';     }          return 0; }</pre><p><br/></p>
这道题暂未补解析。