| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
100 |
| 用户昵称 |
Yis |
运行时间 |
0.836 s |
| 代码语言 |
C++ |
内存使用 |
31.02 MiB |
| 提交时间 |
2026-03-01 12:58:22 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100050;
long long st[maxn][18],stv[maxn][18],fa[maxn],fav[maxn],dep[maxn],stm[maxn][18];
long long head[maxn],nxt[2*maxn],val[2*maxn],to[2*maxn],cnt=0;
void addedge(long long u,long long v,long long w){
cnt++;
to[cnt]=v;
val[cnt]=w;
nxt[cnt]=head[u];
head[u]=cnt;
}
long long n,q,k,iskey[maxn],keycnt[maxn],minkey[maxn],minkey2[maxn];
void dfs1(long long now,long long last){
if(head[now]==0){
if(iskey[now]){
minkey[now]=0;
keycnt[now]=1;
minkey2[now]=0;
}
}else{
if(iskey[now]){
minkey2[now]=0;
minkey[now]=0;
keycnt[now]=1;
}
long long ed=head[now];
while(ed){
if(to[ed]!=last){
dep[to[ed]]=dep[now]+1;
dfs1(to[ed],now);
fav[to[ed]]=val[ed];
fa[to[ed]]=now;
if(keycnt[to[ed]]){
minkey[now]=min(minkey[now],minkey[to[ed]]+val[ed]);
keycnt[now]+=keycnt[to[ed]];
}
}
ed=nxt[ed];
}
}
}
void build(){
for(long long i=1;i<=n;i++){
st[i][0]=i;
st[i][1]=fa[i];
stv[i][0]=0;
stv[i][1]=fav[i];
}
for(long long log=2;log<18;log++){
for(long long i=1;i<=n;i++){
if(dep[i]>=1<<log){
st[i][log]=st[fa[st[i][log-1]]][log-1];
stv[i][log]=stv[i][log-1]+fav[st[i][log-1]]+stv[fa[st[i][log-1]]][log-1];
}
}
}
}
long long cost=0;
long long glog2(long long n){
long long h=0,t=n;
while(t>1){
t=t>>1;
h++;
}
return h;
}
long long todep(long long ind,long long depth){
if(dep[ind]==depth)return ind;
long long i=dep[ind]-depth+1;
long long t=glog2(i);
cost+=stv[ind][t];
return todep(st[ind][t],depth);
}
long long lca(long long a,long long b){
if(dep[a]<dep[b])return lca(b,a);
if(a==b)return b;
a=todep(a,dep[b]);
if(a==b)return b;
while(1){
if(a==b)return a;
if(fa[a]==fa[b]){
cost+=fav[a]+fav[b];
return fa[a];
}
for(long long i=18;i-->0;){
if(1<<i<=dep[a]&&st[a][i]!=st[b][i]){
cost+=stv[a][i]+stv[b][i];
a=st[a][i];
b=st[b][i];
}
}
}
}
void dfs2(long long now,long long last){
if(head[now]==0)return ;
long long ed=head[now];
while(ed){
if(to[ed]!=last){
minkey2[to[ed]]=min(minkey[to[ed]],minkey2[now]+val[ed]);
dfs2(to[ed],now);
}
ed=nxt[ed];
}
}
void build2(){
for(long long i=1;i<=n;i++){
stm[i][0]=minkey2[i];
stm[i][1]=min(minkey2[i],minkey2[fa[i]]);
}
for(long long log=2;log<18;log++){
for(long long i=1;i<=n;i++){
if(dep[i]>=1<<log){
stm[i][log]=min(stm[i][log-1],stm[fa[st[i][log-1]]][log-1]);
}
}
}
}
long long findstm(long long a,long long b){
if(a==b)return minkey2[b];
long long i=dep[a]-dep[b]+1;
long long t=glog2(i);
if(1<<t!=i)
return min(stm[a][t],findstm(fa[st[a][t]],b));
else return stm[a][t];
}
long long quest(long long s,long long t){
cost=0;
long long l=lca(s,t);
return cost+2*min(findstm(s,l),findstm(t,l));
}
int main(){
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q>>k;
long long u,v,w;
for(long long i=0;i<maxn;i++){
minkey[i]=1<<30;
minkey2[i]=1<<30;
}
for(long long i=0;i<n-1;i++){
cin>>u>>v>>w;
addedge(u,v,w);
addedge(v,u,w);
}
long long key=0;
for(long long i=0;i<k;i++){
cin>>key;
iskey[key]=1;
}
dep[1]=1;
dfs1(1,0);
build();
minkey2[1]=minkey[1];
dfs2(1,0);
build2();
long long s,t;
while(q--){
cin>>s>>t;
cout<<quest(s,t)<<'\n';
}
cout.flush();
return 0;
}