比赛 寒假集训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;
}