玄关82pts
查看原帖
玄关82pts
1098596
WhiteNight__楼主2024/7/22 21:25

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;
}

谢谢大佬!!!

2024/7/22 21:25
加载中...