RE第3个点,WA第9个点。普通的 LCA 做法。查了很久没有查出问题。
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 40050
#define ll long long
#define abs(x) (((x) > 0) ? (x) : -(x))
ll n , m , cnt , ans , last , lg[150] , head[MAXN] , fa[MAXN][150] , dep[MAXN];
struct Edge {
ll to , next;
}edge[MAXN*3];
void add (ll in , ll ou)
{
++ cnt;
edge[cnt] = {ou , head[in]};
head[in] = cnt;
}
void dfs (ll now , ll fat)
{
fa[now][0] = fat , dep[now] = dep[fat] + 1;
for(int i = 1 ; i <= lg[dep[now]]+1 ; i ++)
fa[now][i] = fa[fa[now][i-1]][i-1];
for(int i = head[now] ; i ; i = edge[i].next)
{
const int to = edge[i].to;
if(to != fat)
dfs (to , now);
}
}
ll ask (ll x , ll y)
{
if(dep[x] < dep[y])
x ^= y ^= x ^= y;
ll yu_x = x , yu_y = y;
while (dep[x] > dep[y])
x = fa[x][lg[dep[x] - dep[y]]];
if(x == y)
return abs(dep[yu_x] - dep[yu_y]);
for(int i = lg[dep[x]] ; i >= 0 ; i --)
if(fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
return dep[yu_x] + dep[yu_y] - 2 * dep[fa[x][0]];
}
int main()
{
scanf("%lld",&n);
for(ll i = 1 ; i <= n-1 ; i ++)
{
ll u , v;
scanf("%lld%lld",&u,&v);
add (u , v);
add (v , u);
}
for(ll i = 2 ; i <= 140 ; i ++)
lg[i] = lg[i-1] + (ll)(1 << (lg[i-1]+1) == i);
dfs (1 , 0);
scanf("%lld",&m);
last = 1;
for(ll i = 1 ; i <= m ; i ++)
{
ll u;
scanf("%lld",&u);
ans += ask (last , u);
last = u;
}
printf("%lld\n",ans);
return 0;
}
谢谢大佬!!!