P8820 [CSP-S 2022] 数据传输
St_john
·
·
个人记录
P8820
首先可以数据点分治。
$k=2$ 就是路径上进行 DP。
$k=3$ 可以拿其他点来进行中转。
研究通解。
设 $fa_{i,j}$ 表示 $i$ 的第 $2^j$ 级祖先。
设 $f_{i,j,x,y}$ 表示 $i$ 到 $fa_{i,j}$，初始到 $i$ 已经有 $x$ 个点跳过了，最后到 $fa_{i,j}$ 已经有 $y$ 个点被跳过了。
$f$ 初始值直接赋为 $+\infty$。
转移就很显然了。
当然，对不同的 $k$，进行的讨论也不同。
当 $k=1$ 时，$f_{i,0,0,0}=v_{fa_{i,0}}$。
当 $k=2$ 时，$f_{i,0,0,0}=f_{i,0,1,0}=v_{fa_{i,0}},f_{i,0,0,1}=0$。
当 $k=3$ 时，$f_{i,0,0,0}=f_{i,0,1,0}=f_{i,0,2,0}=v_{fa_{i,0}},f_{i,0,0,1}=f_{i,0,1,2}=0,f_{i,0,2,2}=g_{i}$。
这里设 $g_{i}=\min_{(i,j)\in E} v_j$。
在求解时，也要分别讨论。
令 $z=lca(x,y)$，计算 $(x,0)\to (z,0/1/2),(y,0)\to (z,0/1/2)$ 的状况即可。
对于答案，直接将两边拼起来，进行讨论即可。
对于 $k=3$ 的情况，记得引用 $z$ 周围的点。
在多算的情况减去 $z$ 的权值。
```cpp
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
#define il inline
#define pc putchar
#define Re register int
#define _for(i,a,b) for(register int i=(a);i<=(b);++i)
#define __for(i,a,b) for(register int i=(a);i>=(b);--i)
il int re(){
int x=0;
char ch=getchar();
bool f=0;
while(ch<'0'||ch>'9')
f|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
void pr(ll x){
if(x<0) x=-x,pc('-');
if(x>9) pr(x/10);
pc(x%10|48);
}
const int A=2e5+10,B=A<<1;
int n,q,K,v[A];
int head[A],cnt;
struct Edge{
int t,n;
}edge[B];
il void add_edge(int u,int v){
edge[++cnt]=(Edge){v,head[u]};head[u]=cnt;
edge[++cnt]=(Edge){u,head[v]};head[v]=cnt;
}
int dep[A],fa[A][20],g[A];
ll f[A][20][3][3];
il ll min(ll a,ll b){
return a<b?a:b;
}
void dfs(int x){
if(K==1){
f[x][0][0][0]=v[fa[x][0]];
}
else if(K==2){
f[x][0][0][0]=f[x][0][1][0]=v[fa[x][0]];
f[x][0][0][1]=0;
}
else{
f[x][0][0][0]=f[x][0][1][0]=f[x][0][2][0]=v[fa[x][0]];
f[x][0][0][1]=f[x][0][1][2]=0;
f[x][0][2][2]=g[x];
}
_for(i,1,19)
for(Re a=0;a<K;++a)
for(Re b=0;b<K;++b)
for(Re c=0;c<K;++c)
f[x][i][a][b]=min(f[x][i][a][b],f[x][i-1][a][c]+f[fa[x][i-1]][i-1][c][b]);
for(Re i=head[x],y;i;i=edge[i].n){
y=edge[i].t;
if(y!=fa[x][0]){
dep[y]=dep[x]+1;
fa[y][0]=x;
_for(i,1,19)
fa[y][i]=fa[fa[y][i-1]][i-1];
dfs(y);
}
}
}
il void swap(int &x,int &y){
x^=y^=x^=y;
}
il int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
__for(i,19,0)
if(fa[x][i]&&dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y) return x;
__for(i,19,0)
if(fa[x][i]&&fa[y][i]&&fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
il vector<ll> calc(int x,int y){
vector<ll> v1;
v1.resize(3);
v1[0]=v1[1]=v1[2]=v[x];
__for(i,19,0)
if(fa[x][i]&&dep[fa[x][i]]>=dep[y]){
vector<ll> v2=v1;
v1[0]=v1[1]=v1[2]=1e18;
for(Re a=0;a<K;++a)
for(Re b=0;b<K;++b)
v1[a]=min(v1[a],v2[b]+f[x][i][b][a]);
x=fa[x][i];
}
return v1;
}
il ll solve(int x,int y){
ll ans=1e18;
int z=lca(x,y);
vector<ll> v1=calc(x,z),v2=calc(y,z);
ans=v1[0]+v2[0]-v[z];
for(Re i=0;i<K;++i)
for(Re j=0;j<K;++j)
ans=min(ans,v1[i]+v2[j]+(i+j>K)*g[z]);
return ans;
}
signed main(){
n=re(),q=re(),K=re();
_for(i,1,n) g[i]=v[i]=re();
memset(f,0x3f,sizeof(f));
_for(i,2,n){
int x=re(),y=re();
add_edge(x,y);
if(g[x]>v[y]) g[x]=v[y];
if(g[y]>v[x]) g[y]=v[x];
}
dfs(1);
while(q--)
pr(solve(re(),re())),pc('\n');
return 0;
}
```