| 比赛 |
寒假集训5 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
白色相簿的季节 |
最终得分 |
100 |
| 用户昵称 |
PXCZM |
运行时间 |
0.900 s |
| 代码语言 |
C++ |
内存使用 |
20.36 MiB |
| 提交时间 |
2026-03-01 09:47:24 |
显示代码纯文本
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,q,k;
vector<pair<int,int> >a[100010];
int kk[100010];
ll d[100010],val[100010];
priority_queue<pair<ll,int> >p;
bool vis[100010];
struct node
{
int fa,dep,son,siz,dfn,top;
ll sum;
node(){fa=dep=son=siz=dfn=top=sum=0;}
}z[100010];
void dfs1(int rt,int fa,int deep)
{
z[rt].fa=fa;
z[rt].dep=deep;
z[rt].siz=1;
int len=a[rt].size(),maxson=0;
for(int i=0;i<len;i++)
{
int to=a[rt][i].second;
if(to==fa)
{
z[rt].sum=a[rt][i].first;
continue;
}
dfs1(to,rt,deep+1);
z[rt].siz+=z[to].siz;
if(z[to].siz>maxson)
{
maxson=z[to].siz;
z[rt].son=to;
}
}
}
int cnt;
void dfs2(int rt,int topf)
{
z[rt].dfn=++cnt;
z[rt].top=topf;
val[cnt]=d[rt];
int len=a[rt].size();
for(int i=0;i<len;i++)
{
int to=a[rt][i].second;
if(to==z[rt].fa)
{
z[rt].sum+=z[to].sum;
break;
}
}
if(z[rt].son) dfs2(z[rt].son,topf);
for(int i=0;i<len;i++)
{
int to=a[rt][i].second;
if(to==z[rt].son||to==z[rt].fa) continue;
dfs2(to,to);
}
}
ll f[100010][20];
void ST()
{
for(int i=1;i<=n;i++) f[i][0]=val[i];
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
ll query(int x,int y)
{
int tmp=log2(y-x+1);
return min(f[x][tmp],f[y-(1<<tmp)+1][tmp]);
}
void solve(int x,int y)
{
ll ans=0,minn=1e18;
int topx=z[x].top,topy=z[y].top;
while(topx!=topy)
{
if(z[topx].dep<z[topy].dep)
{
swap(topx,topy);
swap(x,y);
}
minn=min(minn,query(z[topx].dfn,z[x].dfn));
ans+=z[x].sum-z[z[topx].fa].sum;
x=z[topx].fa;
topx=z[x].top;
}
if(z[x].dep>z[y].dep) swap(x,y);
minn=min(minn,query(z[x].dfn,z[y].dfn));
ans+=z[y].sum-z[x].sum;
cout<<ans+minn<<'\n';
}
int main()
{
freopen("wa.in","r",stdin);
freopen("wa.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>q>>k;
for(int i=1;i<n;i++)
{
int u,v,w;cin>>u>>v>>w;
a[u].push_back(make_pair(w,v));
a[v].push_back(make_pair(w,u));
}
for(int i=1;i<=n;i++) d[i]=1e17;
for(int i=1;i<=k;i++)
{
cin>>kk[i];
d[kk[i]]=0;
p.push(make_pair(0,kk[i]));
}
while(p.size())
{
int h=p.top().second;
p.pop();
if(vis[h]) continue;
vis[h]=1;
int len=a[h].size();
for(int i=0;i<len;i++)
{
ll w=a[h][i].first*2;
int to=a[h][i].second;
if(d[to]>d[h]+w)
{
d[to]=d[h]+w;
p.push(make_pair(-d[to],to));
}
}
}
dfs1(1,0,1);
dfs2(1,1);
ST();
while(q--)
{
int x,y;
cin>>x>>y;
solve(x,y);
}
return 0;
}