| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAATA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
90 |
| 用户昵称 |
KKZH |
运行时间 |
2.631 s |
| 代码语言 |
C++ |
内存使用 |
45.95 MiB |
| 提交时间 |
2026-03-01 10:05:56 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
const int M=21;
int n,q,k,cnt,f[N],head[N],dis[N],ok,mn,all,dep[N];
struct node{
int nxt,to,wei;
}ed[N];
struct node1{
int dis,to,yes,len;
}fa[N][30];
void add(int x,int y,int z){
ed[++cnt].nxt=head[x];
head[x]=cnt;
ed[cnt].to=y;
ed[cnt].wei=z;
}
void dfs(int x,int now,int tot,int fa){
if(f[x]==1){
dis[now]=min(tot,dis[now]);
return;
}
for(int i=head[x];i!=0;i=ed[i].nxt){
int y=ed[i].to;
if(y==fa) continue;
if(y<now){
dis[now]=min(dis[y]+tot+ed[i].wei,dis[now]);
}else{
dfs(y,now,ed[i].wei+tot,x);
}
}
}
void dfs1(int x,int fat,int lent){
dep[x]=dep[fat]+1;
fa[x][0].to=fat;
fa[x][0].len=lent;
fa[x][0].dis=min(dis[x],dis[fat]);
fa[x][0].yes=(f[fat]|f[x]);
// cout<<x<<endl;
// cout<<fa[x][0].len<<" "<<fa[x][0].to<<" "<<fa[x][0].dis<<" "<<fa[x][0].yes<<endl;
for(int i=1;i<=M;i++){
fa[x][i].len=fa[fa[x][i-1].to][i-1].len+fa[x][i-1].len;
fa[x][i].to=fa[fa[x][i-1].to][i-1].to;
fa[x][i].dis=min(fa[fa[x][i-1].to][i-1].dis,fa[x][i-1].dis);
fa[x][i].yes=(fa[fa[x][i-1].to][i-1].yes|fa[x][i-1].yes);
// cout<<fa[x][i].len<<" "<<fa[x][i].to<<" "<<fa[x][i].dis<<" "<<fa[x][i].yes<<endl;
}
for(int i=head[x];i!=0;i=ed[i].nxt){
int y=ed[i].to;
if(y==fat) continue;
dfs1(y,x,ed[i].wei);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]){
ok=(ok|fa[x][__lg(dep[x]-dep[y])].yes);
all+=fa[x][__lg(dep[x]-dep[y])].len;
mn=min(mn,fa[x][__lg(dep[x]-dep[y])].dis);
x=fa[x][__lg(dep[x]-dep[y])].to;
}
// cout<<dep[x]<<" "<<dep[y]<<endl;
if(x==y) return x;
for(int i=M;i>=0;i--){
if(fa[x][i].to!=fa[y][i].to){
all+=fa[x][i].len+fa[y][i].len;
ok=(ok|(fa[x][i].yes|fa[y][i].yes));
mn=min(mn,min(fa[x][i].dis,fa[y][i].dis));
x=fa[x][i].to;
y=fa[y][i].to;
// cout<<mn<<" "<<all<<" "<<ok<<endl;
}
}
all+=fa[x][0].len+fa[y][0].len;
ok=(ok|(fa[x][0].yes|fa[y][0].yes));
mn=min(mn,min(fa[x][0].dis,fa[y][0].dis));
return fa[x][0].to;
}
signed main(){
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>q>>k;
int x,y,z;
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<n;i++){
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
for(int i=1;i<=k;i++){
cin>>x;
f[x]=1;
}
for(int i=1;i<=n;i++)
dfs(i,i,0,0);
dfs1(1,0,0);
for(int i=1;i<=q;i++){
cin>>x>>y;
if(x==y&&f[x]==1){
cout<<0<<endl;
continue;
}
if(x==y){
cout<<dis[x]*2<<endl;
continue;
}
ok=all=0;
mn=INT_MAX;
z=LCA(x,y);
if(ok==1){
cout<<all<<endl;
}else{
cout<<all+mn*2<<endl;
}
}
}