#include<bits/stdc++.h>
#define E(v, w) (Edge){v, w}
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
inline int read(){
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int n, q, k, f[MAXN], pre[MAXN], a[MAXN], tot, st1[MAXN][20], b[MAXN], st2[MAXN][20];
int fa[MAXN], Bigson[MAXN], dep[MAXN], top[MAXN], siz[MAXN], dfn[MAXN], id[MAXN];
struct Edge{
int v, w;
};
vector <Edge> tr[MAXN];
struct Node{
int u, val, idd;
bool operator < (Node x) const {return this->idd < x.idd;}
bool operator > (Node x) const {return this->idd > x.idd;}
bool operator == (Node x) const {return this->idd == x.idd;}
}p[MAXN];
void dfs1(int u, int Fa){
dep[u] = dep[Fa] + 1;
fa[u] = Fa;
siz[u] = 1;
int len = tr[u].size();
for(int i = 0; i < len; i++){
int v = tr[u][i].v, w = tr[u][i].w;
if(v == Fa) continue;
pre[v] = pre[u] + w;
a[v] = w;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > siz[Bigson[u]])
Bigson[u] = v;
}
}
void dfs2(int u, int head){
dfn[++tot] = u;
id[u] = tot;
// cout << u << ' ' << id[u] << endl;
top[u] = head;
if(Bigson[u])
dfs2(Bigson[u], head);
int len = tr[u].size();
for(int i = 0; i < len; i++){
int v = tr[u][i].v;
if(v == Bigson[u] || v == fa[u]) continue;
dfs2(v, v);
}
}
bool cmp(Node x, Node y){
return x.idd < y.idd;
}
void init1(){
for(int i = 1; i <= k; i++)
st1[i][0] = p[i].val;
for(int j = 1; j <= 20; j++){
for(int l = 1, r = l + (1<<j) - 1; r <= n; l++, r++)
st1[l][j] = min(st1[l][j-1], st1[r-(1<<(j-1))+1][j-1]);
}
}
int query1(int l, int r){
int lg = log2(r-l+1);
return min(st1[l][lg], st1[r-(1<<lg)+1][lg]);
}
int work(int u){
int l = id[u], r = id[u] + siz[u] - 1;
int L = lower_bound(p+1, p+1+k, (Node){-1, -1, l}) - p;
int R = upper_bound(p+1, p+1+k, (Node){-1, -1, r}) - p - 1;
if(L > R) return INT_MAX;
return query1(L, R);
}
void dfs3(int u){
f[u] = work(u) - pre[u];
int len = tr[u].size();
for(int i = 0; i < len; i++){
int v = tr[u][i].v, w = tr[u][i].w;
if(v == fa[u]) continue;
dfs3(v);
f[v] = min(f[v], f[u] + w);
}
}
void init2(){
for(int i = 1; i <= n; i++)
st2[i][0] = f[dfn[i]];
for(int j = 1; j <= 20; j++){
for(int l = 1, r = l + (1<<j) - 1; r <= n; l++, r++)
st2[l][j] = min(st2[l][j-1], st2[r-(1<<(j-1))+1][j-1]);
}
}
int query2(int l, int r){
int lg = log2(r-l+1);
return min(st2[l][lg], st2[r-(1<<lg)+1][lg]);
}
pair <int,int> query_path(int u, int v){
int res = INT_MAX;
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]])
swap(u, v);
res = min(res, query2(id[top[u]], id[u] ));
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
res = min(res, query2(id[v], id[u]));
return {v, res};
}
signed main(){
n = read(), q = read(), k = read();
for(int i = 1; i < n; i++){
int u = read(), v = read(), w = read();
tr[u].push_back(E(v, w));
tr[v].push_back(E(u, w));
}
dfs1(1, 0);
dfs2(1, 1);
for(int i = 1; i <= k; i++)
p[i].u = read(), p[i].idd = id[p[i].u], p[i].val = pre[p[i].u];
sort(p+1, p+1+k, cmp);
init1();
dfs3(1);
init2();
while(q--){
int u = read(), v = read();
pair <int,int> tmp = query_path(u, v);
int lca = tmp.first, az = tmp.second;
// cout << pre[u] << ' ' << pre[v] << ' ' << lca<< endl;
printf("%lld\n", pre[u] + pre[v] - 2*pre[lca] + 2*az);
}
return 0;
}
不知道为什么,只拿了 20 分,hack 数据也过了。帮帮我吧,QWQ