练习倍增LCA商务旅行（Travelling Salesman）debug Wrong Ans

常规
1 
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30005;

struct Node { int to, nxt; } G[N << 1];
int n, m, head[N], cnt, lg2[N];
int deep[N], fa[N][30]; // 30: about log2(N)+1

void add(int u, int v) {
	G[++cnt].to = v;
	G[cnt].nxt  = head[u];
	head[u]     = cnt;
}

void Init_Deep(int now, int father) {
	deep[now]  = deep[father] + 1;
	fa[now][0] = father;
	
	for(int i = 1;i <= lg2[deep[now]];i++) {
		fa[now][i] = fa[fa[now][i-1]][i-1];
	}
	for(int i = head[now];i;i = G[i].nxt) {
		if(G[i].to != father) Init_Deep(G[i].to, now);
	}
}

int LCA(int u, int v) {
	if(deep[u] < deep[v]) {
		swap(u, v);
	}
	while(deep[u] > deep[v]) {
		u = fa[u][lg2[deep[u]-deep[v]]-1];
	}
	if(u == v) return u; // u or v
	for(int k = lg2[deep[u]]-1;k >= 0;k--) {
		if(fa[u][k] != fa[v][k]) {
			u = fa[u][k];
			v = fa[v][k];
		}
	}
	return fa[u][0];
}

long long query_dis(int u, int v) {
	return deep[u] + deep[v] - ((deep[LCA(u, v)]) << 1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int u, v, x, now = 1;
	cin>>n;
	
	for(int i = 2;i <= n+1;i++) {
		lg2[i] = lg2[i << 1] + 1;
	}
	
	for(int i = 1;i < n;i++) {
		cin>>u>>v;
		add(u, v);
		add(v, u);
	}
	Init_Deep(1, 0);
	cin>>m;
	long long dis = 0;
	while(m--) {
		cin>>x;
		dis += query_dis(now, x);
		now = x;
	}
	cout<<dis<<endl;
	return 0;
}

看看哪里错了啊，此代码样例输出11，答案是7

2 个赞
2 
	for(int i = 2;i <= n+1;i++) {
		lg2[i] = lg2[i << 1] + 1;
	}

这里是[i << 1]吗？？？？？？？？

	u = fa[u][lg2[deep[u]-deep[v]] - 1];

这里不该-1，因为lg2是下取整

for(int k = lg2[deep[u]] - 1;k >= 0;k--)

for循环中 k的初值也不应该减一

2 个赞