| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
100 |
| 用户昵称 |
exil |
运行时间 |
1.211 s |
| 代码语言 |
C++ |
内存使用 |
36.91 MiB |
| 提交时间 |
2026-03-01 11:28:37 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> v[100005][2];
int dian[100005];
int shen[100005];
int fa[100005];
int f[100005][40];
int len[100005];
int dis[100005];
int n,k,p;
int st[100005][20];
void chushihua(){
int k = log2(n);
for(int j = 1;j<=k;j++){
for(int i = 1;i<=n;i++){
f[i][j] = f[f[i][j-1]][j-1];
}
}
}
void chushihua2(){
int k = log2(n);
for(int j = 1;j<=k;j++){
for(int i = 1;i<=n;i++){
if(f[i][j]!=0)st[i][j] = min(st[f[i][j-1]][j-1],st[i][j-1]);
}
}
}
int pandeng(int y,int x){
int k = log2(shen[y]);
for(int i = k;i>=0;i--){
if(shen[f[y][i]]>=shen[x])y = f[y][i];
}
return y;
}
int pandeng2(int y,int x){
int k = log2(shen[y]);
for(int i = k;i>=0;i--){
if(shen[f[y][i]]>=shen[x])y = f[y][i];
}
return y;
}
int zui(int x,int y){
int k = log2(shen[x]);
for(int i = k;i>=0;i--){
if(f[x][i]!=f[y][i]){
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
int zui2(int x,int z){
int k = log2(shen[x]);
int ans=dis[x];
for(int i = k;i>=0;i--){
if(shen[f[x][i]]>=shen[z]){
ans=min(ans,st[x][i]);
x = f[x][i];
}
}
return ans;
}
signed main(){
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
scanf("%lld%lld%lld",&n,&p,&k);
for(int i = 1;i<n;i++){
int u,vi,w;
scanf("%lld%lld%lld",&u,&vi,&w);
v[u][0].push_back(vi);
v[vi][0].push_back(u);
v[u][1].push_back(w);
v[vi][1].push_back(w);
dis[i]=-1;
}
dis[n]=-1;
queue<int> qwq;
for(int i = 1;i<=k;i++){
int a;
scanf("%lld",&a);
dian[a]=1;
qwq.push(a);
dis[a]=0;
}
queue<int> q;
q.push(1);
shen[1]=1;
while(!q.empty()){
int d=q.front();
for(int i = 0;i<v[d][0].size();i++){
if(v[d][0][i]==fa[d])continue;
fa[v[d][0][i]]=d;
len[v[d][0][i]]=len[d]+v[d][1][i];
q.push(v[d][0][i]);
shen[v[d][0][i]]=shen[d]+1;
}
q.pop();
}
for(int i = 1;i<=n;i++)f[i][0]=fa[i];
chushihua();
if(k==n){
for(int i = 1;i<=p;i++){
int l,r;
scanf("%lld%lld",&l,&r);
int li=l,ri=r;
if(shen[l]>shen[r])l=pandeng(l,r);
else if(shen[l]<shen[r])r=pandeng(r,l);
int g=0;
if(l==r)g=l;
else g=zui(l,r);
printf("%lld\n",len[li]+len[ri]-len[g]*2);
}
}
else {
while(!qwq.empty()){
int d=qwq.front();
qwq.pop();
for(int i = 0;i<v[d][0].size();i++){
if(dis[v[d][0][i]]==-1){
dis[v[d][0][i]]=dis[d]+v[d][1][i];
qwq.push(v[d][0][i]);
}
else{
if(dis[v[d][0][i]]>dis[d]+v[d][1][i]){
dis[v[d][0][i]]=dis[d]+v[d][1][i];
qwq.push(v[d][0][i]);
}
}
}
}
for(int i = 1;i<=n;i++){
if(fa[i]!=0)st[i][0]=min(dis[i],dis[fa[i]]);
else st[i][0]=dis[i];
}
chushihua2();
// for(int i = 1;i<=n;i++){
// for(int j = 0;j<=10;j++)cout<<st[i][j]<<" ";
// cout<<endl;
// }
for(int i = 1;i<=p;i++){
int l,r;
scanf("%lld%lld",&l,&r);
int li=l,ri=r;
if(shen[l]>shen[r])l=pandeng(l,r);
else if(shen[l]<shen[r])r=pandeng(r,l);
int g=0;
if(l==r)g=l;
else g=zui(l,r);
l=li,r=ri;
int minn=0;
minn=min(zui2(l,g),zui2(r,g));
printf("%lld\n",min(len[li]+len[ri]-len[g]*2+minn*2,len[li]+len[ri]-len[g]*2+minn*2));
}
}
return 0;
}