| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
100 |
| 用户昵称 |
我常常追忆未来 |
运行时间 |
3.001 s |
| 代码语言 |
C++ |
内存使用 |
60.30 MiB |
| 提交时间 |
2026-03-01 09:46:16 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
struct node{
int l,r,minn;
}t[2*N];
struct edge{
int to,val;
};
vector<edge>g[N];
vector<int>G[N];
int cnt,root,tot,n,q,k;
int dis[N],siz[N],son[N],top[N],dep[N],id[N],at[N],f[N],vis[N],to_root[N];
void pushup(int p){
t[p].minn=min(t[t[p].l].minn,t[t[p].r].minn);
}
void build(int &p,int l,int r){
p=++cnt;
if(l==r){
t[p].minn=at[l];
return;
}
int mid=l+r>>1;
build(t[p].l,l,mid);
build(t[p].r,mid+1,r);
pushup(p);
}
int query(int p,int l,int r,int ql,int qr){
if(l>qr||r<ql){
return 1e9;
}
if(ql<=l&&r<=qr){
return t[p].minn;
}
int mid=l+r>>1;
return min(query(t[p].l,l,mid,ql,qr),query(t[p].r,mid+1,r,ql,qr));
}
void dfs1(int u,int fa){
siz[u]=1;
dep[u]=dep[fa]+1;
f[u]=fa;
for(auto v:G[u]){
if(v!=fa){
dfs1(v,u);
siz[u]+=siz[v];
if(!son[u]||siz[son[u]]<siz[v]){
son[u]=v;
}
}
}
}
void dfs2(int u,int topu){
id[u]=++tot;
at[tot]=dis[u];
top[u]=topu;
if(!son[u]){
return;
}
dfs2(son[u],topu);
for(auto v:G[u]){
if(v!=f[u]&&v!=son[u]){
dfs2(v,v);
}
}
}
void dfs3(int u,int fa){
for(auto vv:g[u]){
int v=vv.to,val=vv.val;
if(v!=fa){
to_root[v]=to_root[u]+val;
dfs3(v,u);
}
}
}
void dij(){
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<int,int> >q;
for(int i=1;i<=k;i++){
int u;
cin>>u;
q.push({0,u});
dis[u]=0;
}
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u]){
continue;
}
vis[u]=1;
for(auto vv:g[u]){
int v=vv.to,val=vv.val;
if(dis[v]>dis[u]+val){
dis[v]=dis[u]+val;
q.push({-dis[v],v});
}
}
}
}
int qmin(int x,int y){
int ans=1e9,res=to_root[x]+to_root[y];
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
swap(x,y);
}
ans=min(query(root,1,n,id[top[x]],id[x]),ans);
x=f[top[x]];
}
if(dep[x]<dep[y]){
swap(x,y);
}
ans=min(ans,query(root,1,n,id[y],id[x]));
return (res-2*to_root[y]+ans*2);
}
int main(){
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
cin>>n>>q>>k;
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
G[u].push_back(v);
G[v].push_back(u);
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dij();
dfs1(1,0);
dfs2(1,1);
dfs3(1,0);
build(root,1,n);
for(int i=1;i<=q;i++){
int s,t;
cin>>s>>t;
cout<<qmin(s,t)<<"\n";
}
return 0;
}