| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
100 |
| 用户昵称 |
123 |
运行时间 |
2.038 s |
| 代码语言 |
C++ |
内存使用 |
19.21 MiB |
| 提交时间 |
2026-03-01 09:16:59 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e5+10,K=22;
int n,k,a[N],head[N],idx[M],nxt[M],val[M],tot=0,dis[N],vis[N],f[N][K],d[N][K],e,depth[N],w[N][K];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int> > > q;
void add(int x,int y,int z)
{
idx[++tot]=y;
val[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
void dijkstra()
{
memset(dis,0x3f,sizeof(dis));
for (int i=1;i<=k;i++)
{
q.push({0,a[i]});
dis[a[i]]=0;
}
while (!q.empty())
{
int t=q.top().second;q.pop();
if (vis[t]) continue;
vis[t]=1;
for (int i=head[t];i;i=nxt[i])
{
int y=idx[i];
if (dis[y]>dis[t]+val[i])
{
dis[y]=dis[t]+val[i];
if (!vis[y]) q.push({dis[y],y});
}
}
}
}
void dfs(int now,int fa)
{
f[now][0]=fa,d[now][0]=min(dis[now],dis[fa]),depth[now]=depth[fa]+1;
for (int i=1;i<=20;i++) f[now][i]=f[f[now][i-1]][i-1],d[now][i]=min(d[now][i-1],d[f[now][i-1]][i-1]),w[now][i]=w[now][i-1]+w[f[now][i-1]][i-1];
for (int i=head[now];i;i=nxt[i])
{
int y=idx[i];
if (y==fa) continue;
w[y][0]=val[i];
dfs(y,now);
}
}
long long lca(int x,int y)
{
if (depth[x]<depth[y]) swap(x,y);
long long mi=min(2ll*dis[x],2ll*dis[y]),ans=0;
for (int i=20;i>=0;i--)
{
if (depth[f[x][i]]>=depth[y])
{
ans+=w[x][i];
mi=min(mi,2ll*d[x][i]);
x=f[x][i];
}
}
if (x==y) return mi+ans;
for (int i=20;i>=0;i--)
{
if (f[x][i]!=f[y][i])
{
ans+=w[x][i]+w[y][i];
mi=min(mi,min(2ll*d[x][i],2ll*d[y][i]));
x=f[x][i],y=f[y][i];
}
}
ans+=w[x][0]+w[y][0];
mi=min(mi,min(2ll*d[x][0],2ll*d[y][0]));
return ans+mi;
}
int main() {
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
cin>>n>>e>>k;
for (int i=1;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z),add(y,x,z);
}
for (int i=1;i<=k;i++) cin>>a[i];
dijkstra();
dfs(1,0);
while (e--)
{
int x,y;
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
}