| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
100 |
| 用户昵称 |
李金泽 |
运行时间 |
0.883 s |
| 代码语言 |
C++ |
内存使用 |
24.79 MiB |
| 提交时间 |
2026-03-01 09:26:55 |
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 100005
#define int long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int n,m,k,h[N],cnt,d[N],dp[N],dep[N],fa[N][21],g[N][21],ans,op,x,y,z;
const int inf=1e18;
bool b[N];
struct node{int u,w;bool operator<(node y)const{return w>y.w;}};
struct edge{int v,n,w;}e[N<<1];
void ad(int u,int v,int w){e[++cnt]={v,h[u],w};h[u]=cnt;}
priority_queue<node>q;
void swap(int &x,int &y){int t=x;x=y;y=t;}
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
void dfs(int u,int f)
{
dp[u]=dp[fa[u][0]=f]+1;
g[u][0]=min(d[u],f?d[f]:inf);
for(int i=h[u];i;i=e[i].n)
{
int v=e[i].v,w=e[i].w;
if(v!=f)dep[v]=dep[u]+w,dfs(v,u);
}
}
void init()
{
fo(k,1,20)
fo(i,1,n)
fa[i][k]=fa[fa[i][k-1]][k-1],
g[i][k]=min(g[i][k-1],g[fa[i][k-1]][k-1]);
}
node lca(int x,int y)
{
int ans=min(d[x],d[y]);
if(dp[x]<dp[y])swap(x,y);
rf(k,20,0)
if(fa[x][k]&&dp[fa[x][k]]>=dp[y])
ans=min(ans,g[x][k]),x=fa[x][k];
if(x==y)return {x,ans};
rf(k,20,0)
if(fa[x][k]^fa[y][k])
ans=min(ans,min(g[x][k],g[y][k])),x=fa[x][k],y=fa[y][k];
return {fa[x][0],min(ans,min(g[x][0],g[y][0]))};
}
int read(){
int sum=0;bool f=0;char c=getchar();
for(;c<48||c>57;c=getchar())if(c==45)f=1;
for(;c>=48&&c<=57;c=getchar())sum=sum*10+(c&15);
return f?-sum:sum;
}
signed main(){
freopen("wa.in","r",stdin);freopen("wa.out","w",stdout);
memset(d,0x3f,sizeof(d));
n=read();m=read();k=read();
fo(i,1,n-1)x=read(),y=read(),z=read(),ad(x,y,z),ad(y,x,z);
fo(i,1,k)x=read(),d[x]=0,q.push({x,0});
while(q.size())
{
node u=q.top();q.pop();
if(b[u.u])continue;
b[u.u]=1;
for(int i=h[u.u];i;i=e[i].n)
{
int v=e[i].v,w=u.w+e[i].w;
if(w<d[v])
{
d[v]=w;
q.push({v,w});
}
}
}
dfs(1,0);init();
while(m--)
{
x=read();y=read();
node u=lca(x,y);
printf("%lld\n",dep[x]+dep[y]-2*dep[u.u]+2*u.w);
}
return 0;
}