| 记录编号 |
577549 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[CSP 2022S]数据传输 |
最终得分 |
100 |
| 用户昵称 |
 yrtiop |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
16.425 s |
| 提交时间 |
2022-11-09 10:52:10 |
内存使用 |
0.00 MiB |
显示代码纯文本
// Problem: P8820 [CSP-S 2022] 数据传输
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8820
// Memory Limit: 1 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
using i64 = long long;
const i64 INF = 1e16;
const int maxn = 2e5 + 5;
std::vector<int> G[maxn];
int n,m;
int f[maxn][20],lg[maxn],dep[maxn];
i64 d[maxn],val[maxn],b[maxn];
void dfs(int u,int fa) {
d[u] = d[fa] + val[u];
for(auto& v : G[u]) {
if(v == fa)continue ;
dep[v] = dep[u] + 1;
f[v][0] = u;
for(int k = 1;(1 << k) <= dep[v];++ k)
f[v][k] = f[f[v][k - 1]][k - 1];
dfs(v , u);
}
return ;
}
int LCA(int u,int v) {
if(dep[u] < dep[v])std::swap(u , v);
for(int k = lg[dep[u]];~ k;-- k) {
if(dep[u] - (1 << k) >= dep[v]) {
u = f[u][k];
}
if(u == v)return u;
}
for(int k = lg[dep[u]];~ k;-- k) {
if(f[u][k] != f[v][k]) {
u = f[u][k];
v = f[v][k];
}
}
return f[u][0];
}
namespace subtask_1 {
int main() {
while(m --) {
int u,v;
scanf("%d %d",&u,&v);
int t = LCA(u , v);
printf("%lld\n",d[u] + d[v] - d[t] - d[f[t][0]]);
}
return 0;
}
}
namespace subtask_2 {
struct matrix {
i64 g[2][2];
matrix() {
g[0][0] = g[0][1] = g[1][0] = g[1][1] = INF;
}
void init() {
g[0][0] = g[0][1] = g[1][0] = g[1][1] = INF;
return ;
}
matrix operator * (const matrix& p)const {
matrix a;
for(int q = 0;q < 2;++ q) {
for(int i = 0;i < 2;++ i) {
for(int j = 0;j < 2;++ j) {
a.g[i][j] = std::min(a.g[i][j] , g[i][q] + p.g[q][j]);
}
}
}
return a;
}
}S[maxn][18];
void DFS(int u,int fa) {
for(auto& v : G[u]) {
if(v == fa)continue ;
S[v][0].g[0][0] = val[v];
S[v][0].g[0][1] = 0;
S[v][0].g[1][0] = val[v];
S[v][0].g[1][1] = INF;
for(int k = 1;(1 << k) <= dep[v];++ k)
S[v][k] = S[v][k - 1] * S[f[v][k - 1]][k - 1];
DFS(v , u);
}
return ;
}
int main() {
S[1][0].g[0][0] = val[1];
S[1][0].g[0][1] = 0;
S[1][0].g[1][0] = val[1];
S[1][0].g[1][1] = INF;
DFS(1 , 0);
while(m --) {
int u,v,t;
scanf("%d %d",&u,&v);
if(u == v) {
printf("%lld\n",val[u]);
continue ;
}
t = LCA(u , v);
i64 ans = INF;
matrix F,P;
F.g[0][0] = val[u];
P.g[0][0] = val[v];
int x = f[u][0];
if(u != t) {
for(int k = lg[dep[x]];~ k;-- k) {
if(dep[x] < dep[t])break ;
if(dep[f[x][k]] >= dep[t]) {
F = F * S[x][k];
x = f[x][k];
}
}
while(dep[x] >= dep[t])F = F * S[x][0],x = f[x][0];
}
if(v != t) {
x = f[v][0];
for(int k = lg[dep[x]];~ k;-- k) {
if(dep[x] < dep[t])break ;
if(dep[f[x][k]] >= dep[t]) {
P = P * S[x][k];
x = f[x][k];
}
}
while(dep[x] >= dep[t])P = P * S[x][0],x = f[x][0];
}
ans = std::min(F.g[0][0] + P.g[0][0] - val[t] , F.g[0][1] + P.g[0][1]);
printf("%lld\n",ans);
}
return 0;
}
}
namespace subtask_3 {
struct matrix {
i64 g[5][5];
matrix() {
for(int i = 0;i < 5;++ i)
for(int j = 0;j < 5;++ j)
g[i][j] = INF;
}
void init() {
for(int i = 0;i < 5;++ i)
for(int j = 0;j < 5;++ j)
g[i][j] = INF;
}
matrix operator * (const matrix& p)const {
matrix c;
for(int k = 0;k < 5;++ k)
for(int i = 0;i < 5;++ i)
for(int j = 0;j < 5;++ j)
c.g[i][j] = std::min(c.g[i][j] , g[i][k] + p.g[k][j]);
return c;
}
}S[maxn][18];
void getinit(int u) {
S[u][0].g[0][0] = val[u];
S[u][0].g[0][1] = 0;
S[u][0].g[0][3] = b[u];
S[u][0].g[1][0] = val[u];
S[u][0].g[1][2] = 0;
S[u][0].g[1][3] = b[u];
S[u][0].g[2][0] = val[u];
S[u][0].g[3][0] = val[u];
S[u][0].g[3][3] = b[u];
S[u][0].g[3][4] = 0;
S[u][0].g[4][0] = val[u];
return ;
}
void DFS(int u,int fa) {
for(auto& v : G[u]) {
if(v == fa)continue ;
getinit(v);
for(int k = 1;(1 << k) <= dep[v];++ k)
S[v][k] = S[v][k - 1] * S[f[v][k - 1]][k - 1];
DFS(v , u);
}
return ;
}
int main() {
for(int i = 1;i <= n;++ i) {
b[i] = INF;
for(auto& v : G[i]) {
b[i] = std::min(b[i] , val[v]);
}
}
getinit(1);
DFS(1 , 0);
while(m --) {
int u,v,t;
scanf("%d %d",&u,&v);
if(u == v) {
printf("%lld\n",val[u]);
continue ;
}
t = LCA(u , v);
i64 ans = INF;
matrix F,P;
F.g[0][0] = val[u];
P.g[0][0] = val[v];
int x = f[u][0];
if(u != t) {
for(int k = lg[dep[x]];~ k;-- k) {
if(dep[x] < dep[t])break ;
if(dep[f[x][k]] >= dep[t]) {
F = F * S[x][k];
x = f[x][k];
}
}
while(dep[x] >= dep[t])F = F * S[x][0],x = f[x][0];
}
if(v != t) {
x = f[v][0];
for(int k = lg[dep[x]];~ k;-- k) {
if(dep[x] < dep[t])break ;
if(dep[f[x][k]] >= dep[t]) {
P = P * S[x][k];
x = f[x][k];
}
}
while(dep[x] >= dep[t])P = P * S[x][0],x = f[x][0];
}
ans = std::min(ans , F.g[0][0] + P.g[0][0] - val[t]);
ans = std::min(ans , F.g[0][3] + P.g[0][3] - b[t]);
ans = std::min(ans , F.g[0][1] + P.g[0][1]);
ans = std::min(ans , F.g[0][1] + P.g[0][2]);
ans = std::min(ans , F.g[0][1] + P.g[0][4]);
ans = std::min(ans , F.g[0][4] + P.g[0][1]);
ans = std::min(ans , F.g[0][2] + P.g[0][1]);
printf("%lld\n",ans);
}
return 0;
}
}
int k;
int main() {
freopen("csp2022_transmit.in","r",stdin);
freopen("csp2022_transmit.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i = 1;i <= n;++ i)
scanf("%lld",&val[i]);
for(int i = 1;i < n;++ i) {
int u,v;
scanf("%d %d",&u,&v);
G[u].pb(v);
G[v].pb(u);
}
dep[0] = -1;
for(int i = 2;i <= n;++ i)
lg[i] = lg[i >> 1] + 1;
dfs(1 , 0);
if(k == 1) {
subtask_1::main();
return 0;
}
if(k == 2) {
subtask_2::main();
return 0;
}
else subtask_3::main();
return 0;
}