| 比赛 |
寒假集训5 |
评测结果 |
AAAAATTTTA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
60 |
| 用户昵称 |
梦那边的追忆SB |
运行时间 |
4.694 s |
| 代码语言 |
C++ |
内存使用 |
17.03 MiB |
| 提交时间 |
2026-03-01 11:20:37 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define foru(a,b,c) for(ll a=b;a<=c;a++)
#define endl '\n'
ll n,q,k,f[100005][20],dep[100005],len[100005];
vector<vector<pair<ll,ll> > >a(100005);
vector<ll>sp;
void dfs(ll u,ll fa){
f[u][0]=fa;
dep[u]=dep[fa]+1;
for(auto vw:a[u]){
ll v=vw.first,w=vw.second;
if(v!=fa){
len[v]=len[u]+w;
dfs(v,u);
}
}
}
ll lca(ll u,ll v){
if(dep[u]>dep[v]){
swap(u,v);
}
ll tmp=dep[v]-dep[u];
for(ll i=0;tmp;i++,tmp>>=1){
if(tmp&1){
v=f[v][i];
}
}
if(v==u)return v;
for(ll i=18;i>=0;i--){
if(f[u][i]!=f[v][i]){
u=f[u][i];
v=f[v][i];
}
}
return f[u][0];
}
void init1(){
foru(i,1,q){
ll s,t;
cin>>s>>t;
ll lcast=lca(s,t);
cout<<len[s]+len[t]-(len[lcast]<<1)<<endl;
}
}
void init2(){
foru(i,1,q){
ll s,t,mi=1e18;
cin>>s>>t;
for(auto u:sp){
ll lcasu=lca(s,u);
ll lcatu=lca(t,u);
mi=min(mi,len[t]+len[u]-(len[lcatu]<<1)+len[s]+len[u]-(len[lcasu]<<1));
}
cout<<mi<<endl;
}
}
int main(){
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q>>k;
foru(i,2,n){
ll u,v,w;
cin>>u>>v>>w;
a[u].push_back({v,w});
a[v].push_back({u,w});
}
foru(i,1,k){
ll u;
cin>>u;
sp.push_back(u);
}
dep[1]=1;
dfs(1,0);
foru(j,1,18){
foru(i,1,n){
f[i][j]=f[f[i][j-1]][j-1];
}
}
if(k==n)init1();
else init2();
return 0;
}