| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
100 |
| 用户昵称 |
ChenBp |
运行时间 |
2.283 s |
| 代码语言 |
C++ |
内存使用 |
8.73 MiB |
| 提交时间 |
2026-03-01 11:39:42 |
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;
const int N=2e5+5;
typedef long long ll;
int hd[N],nxt[N],to[N],vl[N],num=1;
void add(int u,int v,int w) {
num++;
to[num]=v;
vl[num]=w;
nxt[num]=hd[u];
hd[u]=num;
}
int fa[N],dep[N],sz[N],son[N],dfn[N],top[N],c[N],rnk[N],tot=0;
void dfs1(int u,int f) {
fa[u]=f;
dep[u]=dep[f]+1;
sz[u]=1;
for(int i=hd[u]; i; i=nxt[i]) {
int v=to[i];
if(v==f) continue;
c[v]=c[u]+vl[i];
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int ance) {
dfn[u]=++tot;
top[u]=ance;
rnk[tot]=u;
if(!son[u]) return;
dfs2(son[u],ance);
for(int i=hd[u]; i; i=nxt[i]) {
int v=to[i];
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
else y=fa[top[y]];
}
return (dep[x]<dep[y]?x:y);
}
int g[N];
int dis[N];
bool vis[N];
int tr[2*N];
#define mid ((l+r)/2)
#define lc (u*2)
#define rc (u*2+1)
void build(int u,int l,int r){
if(l==r) {
tr[u]=dis[rnk[l]];
return;
}
build(lc,l,mid);
build(rc,mid+1,r);
tr[u]=min(tr[lc],tr[rc]);
}
int ask(int u,int l,int r,int x,int y){
if(x<=l&&r<=y){
return tr[u];
}
int res=0x7f7f7f7f;
if(x<=mid) res=min(res,ask(lc,l,mid,x,y));
if(mid+1<=y) res=min(res,ask(rc,mid+1,r,x,y));
return res;
}
int main() {
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
int n,q,k;
cin>>n>>q>>k;
for(int i=1; i<=n-1; i++) {
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int>>p;
for(int i=1; i<=k; i++) {
cin>>g[i];
dis[g[i]]=0;
p.push(make_pair(0,g[i]));
}
while(!p.empty()) {
int u=p.top().second;
p.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=hd[u]; i; i=nxt[i]) {
int v=to[i];
if(dis[v]>dis[u]+vl[i]) {
dis[v]=dis[u]+vl[i];
p.push(make_pair(-dis[v],v));
}
}
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while(q--){
int s,t;
cin>>s>>t;
int l=lca(s,t);
ll ans=c[s]-c[l]+c[t]-c[l];
int res=0x7f7f7f7f;
while(top[s]!=top[t]){
if(dep[top[s]]<dep[top[t]]) swap(s,t);
res=min(res,ask(1,1,n,dfn[top[s]],dfn[s]));
s=fa[top[s]];
}
if(dep[s]>dep[t]) swap(s,t);
res=min(res,ask(1,1,n,dfn[s],dfn[t]));
cout<<ans+2ll*res<<endl;
}
return 0;
}