| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
100 |
| 用户昵称 |
zhyn |
运行时间 |
1.564 s |
| 代码语言 |
C++ |
内存使用 |
13.53 MiB |
| 提交时间 |
2026-03-01 11:46:27 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define inf 0x7f7f7f7f7f7f7f7f
#define smid int mid=(l+r)/2
int n,m;
struct node{
int v;
ll w;
};
struct edge{
int v;
ll w;
friend bool operator<(edge a,edge b){
return a.w>b.w;
}
};
vector<node>e[maxn];
int num[maxn];
bool vis[maxn];
int f[maxn],siz[maxn],son[maxn],top[maxn],dep[maxn],dfn[maxn],id[maxn];
ll val[maxn];
ll dis[maxn];
int tot=0,k;
priority_queue<edge>q;
ll wd[maxn*4],wm[maxn*4];
void dij(){
for(int i=1;i<=n;i++){
dis[i]=inf;
vis[i]=false;
}
for(int i=1;i<=k;i++){
dis[num[i]]=0;
q.push({num[i],0});
}
while(!q.empty()){
int u=q.top().v;
q.pop();
if(vis[u]){
continue;
}
vis[u]=true;
for(node x:e[u]){
int v=x.v;
ll w=x.w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({v,dis[v]});
}
}
}
}
void dfs1(int u,int fa){
f[u]=fa;
dep[u]=dep[fa]+1;
siz[u]=1;
for(node x:e[u]){
int v=x.v;
ll w=x.w;
if(v==fa){
continue;
}
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]){
son[u]=v;
}
val[v]=w;
}
}
void dfs2(int u,int t){
dfn[u]=++tot;
id[dfn[u]]=u;
top[u]=t;
if(!son[u]){
return;
}
dfs2(son[u],t);
for(node x:e[u]){
int v=x.v;
if(v==f[u]||v==son[u]){
continue;
}
dfs2(v,v);
}
}
void pushup(int u){
wd[u]=wd[u*2]+wd[u*2+1];
wm[u]=min(wm[u*2],wm[u*2+1]);
}
void build(int u,int l,int r){
if(l==r){
wm[u]=dis[id[l]];
wd[u]=val[id[l]];
return;
}
smid;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
pushup(u);
}
ll queryd(int u,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr){
return wd[u];
}
smid;
ll sum=0;
if(ql<=mid){
sum+=queryd(u*2,l,mid,ql,qr);
}
if(qr>mid){
sum+=queryd(u*2+1,mid+1,r,ql,qr);
}
return sum;
}
ll querym(int u,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr){
return wm[u];
}
smid;
ll sum=inf;
if(ql<=mid){
sum=min(sum,querym(u*2,l,mid,ql,qr));
}
if(qr>mid){
sum=min(sum,querym(u*2+1,mid+1,r,ql,qr));
}
return sum;
}
ll query_(int l,int r){
ll sum=0,cnt=inf;
while(top[l]!=top[r]){
if(dep[top[l]]<dep[top[r]]){
swap(l,r);
}
sum+=queryd(1,1,n,dfn[top[l]],dfn[l]);
cnt=min(cnt,querym(1,1,n,dfn[top[l]],dfn[l]));
l=f[top[l]];
}
if(dep[l]>dep[r]){
swap(l,r);
}
if(l!=r){
sum+=queryd(1,1,n,dfn[son[l]],dfn[r]);
}
cnt=min(cnt,querym(1,1,n,dfn[l],dfn[r]));
return sum+cnt*2;
}
int main(){
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<n;i++){
int u,v;
ll w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
for(int i=1;i<=k;i++){
cin>>num[i];
}
dfs1(1,0);
dfs2(1,1);
dij();
build(1,1,n);
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
cout<<query_(u,v)<<"\n";
}
return 0;
}