简要题意
给出一个 \(N\) 个节点的树和一个长度为 \(M\) 的序列 \(S\)。你需要从 \(1\) 出发，依次经过 \(S\) 中的所有点，求至少需要经过的边数。
\(1 \le N \le 30000\)
思路
首先先给出一个结论：树上两点之间的最短离，等于两点的深度和减去其最近公共祖先的两倍。
证明如下（令 \(d(u)\) 为 \(u\) 的深度，\(r\) 为树根，\(a(u,v)\) 为从 \(u\) 到 \(v\) 的最短距离，\(l(u,v)\) 为 \(u,v\) 的最近公共祖先）：
\[\begin{aligned} &d(u)+d(v)-2d(l(u,v))\\ &=a(r,u)+a(r,v)-a(r,l(u,v))-a(r,l(u,v))\\ &=a(l(u,v),u)+a(r,l(u,v))+a(l(u,v),v)+a(r,l(u,v))-a(r,l(u,v))-a(r,l(u,v))\\ &=a(l(u,v),u)+a(l(u,v),v)\\ &=a(u,v) \end{aligned} \]然后的过程就很简单了，使用树剖（用于求最近公共祖先）和上述结论求出 \(a(1,S_1)+a(S_1,S_2)+\cdots+a(S_{M-1}+S_{M})\) 即可。
时间复杂度 \(O(N+M\log N)\)，可以通过本题。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
struct edge {
int nxt, to;
} g[N << 1];
int head[N << 1], ec;
void add(int u, int v) {
g[++ec].nxt = head[u];
g[ec].to = v;
head[u] = ec;
}
int root;
int siz[N], son[N], fa[N], top[N], dep[N];
void dfs1(int u, int father, int deep) {
dep[u] = deep;
siz[u] = 1;
fa[u] = father;
for (int i = head[u]; i; i = g[i].nxt) {
int v = g[i].to;
if (v == father) {
continue;
}
dfs1(v, u, deep + 1);
siz[u] += siz[u];
if (siz[v] >= siz[son[u]]) {
son[u] = v;
}
}
}
void dfs2(int u, int father, int t) {
top[u] = t;
if (son[u])dfs2(son[u], u, t);
for (int i = head[u]; i; i = g[i].nxt) {
int v = g[i].to;
if (v == father) {
continue;
}
if (v == son[u]) {
continue;
}
dfs2(v, u, v);
}
}
int lca(int x, int y) {
int fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] < dep[fy]){
swap(fx, fy);
swap(x, y);
}
x = fa[fx], fx = top[x];
}
if (dep[x] > dep[y]) {
return y;
}
else return x;
}
int n,m,s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
dfs1(1,0,1);
dfs2(1,0,1);
cin>>m;
int ret=0,u=1,v=0;
while(m--){
cin>>v;
ret+=(dep[u]+dep[v]-2*dep[lca(u,v)]); // 运用结论
u=v;
}
cout<<ret;
return 0;
}