点个关注吧
2025-07-12 18:01:22
发布于:广东
29阅读
0回复
0点赞
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pt[200010],q[200010][2],n,m,ui;
long long v[200010],w[200010];
basic_string<int>e[200010],c[200010],s[200010];
void add(int a,int b){w[a]=min(w[a],v[b]),e[a]+=b;}
struct cube{
long long g[3][3];
void clear(){memset(g,0x3f3f,sizeof g);}
void operator =(const int x){
clear();
for(int i=0;i<ui;i++)g[i][0]=v[x];
for(int i=0;i+1<ui;i++)g[i][i+1]=0;
if(ui==3)g[1][1]=w[x];
}
cube operator *(const cube &x){
cube y;y.clear();
for(int i=0;i<ui;i++)for(int j=0;j<ui;j++)for(int k=0;k<ui;k++)
y.g[i][j]=min(y.g[i][j],g[i][k]+x.g[k][j]);
return y;
}
}pv[200010][2],res[200010],zero;
int find(int x){
if(pt[x]==pt[pt[x]])return pt[x];
int z=pt[x];pt[x]=find(pt[x]);
pv[x][0]=pv[x][0]*pv[z][0];
pv[x][1]=pv[z][1]*pv[x][1];
return pt[x];
}
cube qry1(int x){if(x==pt[x])return zero;find(x);return pv[x][0];}
cube qry2(int x){if(x==pt[x])return zero;find(x);return pv[x][1];}
void dfs(int p,int f){
for(int i:s[p]){
if(pt[q[i][1]])swap(q[i][0],q[i][1]);
if(pt[q[i][0]])res[i].clear(),res[i].g[0][0]=v[p],c[find(q[i][0])]+=i,q[i][1]=f;
}
pt[p]=p,pv[p][0]=p,pv[p][1]=p;for(int i:e[p])if(i!=f)dfs(i,p),pt[i]=p;
for(int i:c[p])res[i]=res[i]*qry1(q[i][1])*pv[p][0]*qry2(q[i][0]);
}
int main(){
scanf("%d%d%d",&n,&m,&ui);
for(int i=0;i<ui;i++)for(int j=0;j<ui;j++)if(i!=j)zero.g[i][j]=1e18;
for(int i=1;i<=n;i++)scanf("%lld",&v[i]),w[i]=1e18;
for(int i=1,a,b;i<n;i++)scanf("%d%d",&a,&b),add(a,b),add(b,a);
for(int i=1;i<=m;i++)scanf("%d%d",&q[i][0],&q[i][1]),s[q[i][0]]+=i,s[q[i][1]]+=i;
dfs(1,0);for(int i=1;i<=m;i++)printf("%lld\n",res[i].g[0][0]);
return 0;
}
有帮助,赞一个