RE on 7,求条
查看原帖
RE on 7,求条
960459
__lalala__楼主2025/7/24 13:55
#include<bits/stdc++.h>
using namespace std;
int idx, h[100010], e[100010], ne[100010];
int f[100010][25];
int dep[100010];
int sz[100010];
int n;
inline void add(int a, int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
void dfs(int x, int fa)
{
	dep[x] = dep[fa] + 1;
	f[x][0] = fa;
	sz[x] = 1;
	for(int i = 1;(1 << i) <= n;i++)
	{
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for(int i = h[x];~i;i = ne[i])
	{
		int y = e[i];
		if(y == fa)
		{
			continue;
		}
		dfs(y, x);
		sz[x] += sz[y];
	}
	return;
}
inline int lca(int x, int y)
{
	if(dep[x] < dep[y])
	{
		swap(x, y);
	}
	for(int i = 20;i >= 0;i--)
	{
		if(dep[f[x][i]] >= dep[y])
		{
			x = f[x][i];
		}
	}
	if(x == y)
	{
		return x;
	}
	for(int i = 20;i >= 0;i--)
	{
		if(f[x][i] != f[y][i])
		{
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
inline int find(int x, int k)
{
	if(k > dep[x])
	{
		return 0;
	}
	for(int i = 20;i >= 0;i--)
	{
		if(k >= (1 << i))
		{
			x = f[x][i];
			k -= (1 << i);
		}
	}
	return x;
}
int main(void)
{
	memset(h, -1, sizeof h);
	cin >> n;
	for(int i = 1;i < n;i++)
	{
		int u, v;
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	dfs(1, 0);
	int q;
	cin >> q;
	while(q--)
	{
		int x, y;
		cin >> x >> y;
		if(x == y)
		{
			cout << n << endl;
			continue;
		}
		int l = lca(x, y);
		int num = dep[x] - dep[l] + dep[y] - dep[l];//求两个点之间的点数 
		if(num % 2)
		{
			cout << 0 << endl;
			continue;
		}
		if(dep[x] == dep[y])
		{
			int px = find(x, num / 2 - 1); 
            int py = find(y, num / 2 - 1);
			if(px == 0 || py == 0)
			{
				cout << 0 << endl;
			}
			else
			{
				cout << n - sz[px] - sz[py] << endl;
			}
		}
		else
		{
			num /= 2;
			if(dep[x] < dep[y])
			{
				swap(x, y);
			}
			int mid = find(x, num);
            int child = find(x, num - 1);
            if(mid == 0 || child == 0)
			{
				cout << 0 << endl;
			}
			else
			{
				cout << sz[mid] - sz[child] << endl;
			}
		}
	}
	return 0;
}

用什么办法都行,只要告诉我哪里错了就行,我不会告诉你我其实是用不了AI才求助的

2025/7/24 13:55
加载中...