URAL 1752. Tree 2 樹的直徑+LCA倍增

URAL 1752. Tree 2 樹的直徑+LCA倍增

題目來源：URAL 1752. Tree 2

題意：求一個點v與它距離為d的任意一個點 沒有輸出0

思路：開始想倍增法 但是倍增法只能往他的祖先去 後來百度發現了樹的直徑 想了想 發現可以建2棵樹 每一棵樹的根是樹的直徑的2個端點

這樣保證了每個點和他距離最遠的點就是其中一個根 因為一個點到樹的直徑的端點的距離是最遠的 最後就是LCA倍增了

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 50010;
const int INF = 0x3f3f3f3f;
int anc[maxn][30][2];
int fa[maxn][2], L[maxn], vis[maxn], d[2][maxn], to[maxn];
int n, m;
int first[maxn], cnt;
struct edge
{
	int u, v, next;
}e[maxn*2];

void AddEdge(int u, int v)
{
	e[cnt].v = v;
	e[cnt].next = first[u];
	first[u] = cnt++;
	e[cnt].v = u;
	e[cnt].next = first[v];
	first[v] = cnt++;
}
void pre()
{
	for(int k = 0; k < 2; k++)
	{
		for(int i = 1; i <= n; i++)
		{
			anc[i][0][k] = fa[i][k];
			for(int j = 1; (1<= 0; i--)
	{
		if(d-(1<= 0)
		{
			d -= (1< Q;
	Q.push(u);
	int rt = u, dis = -1;
	while(!Q.empty())
	{
		int x = Q.front(); Q.pop();
		if(d[k][x] > dis)
		{
			dis = d[k][x];
			rt = x;
		}
		for(int i = first[x]; i != -1; i = e[i].next)
		{
			int v = e[i].v;
			if(vis[v])
				continue;
			vis[v] = 1;
			d[k][v] = d[k][x] + 1;
			fa[v][k] = x;
			Q.push(v);
		}
	}
	for(int i = 1; i <= n; i++)
		to[i] = max(to[i], d[k][i]);
	return rt;
}
int main()
{
	while(scanf("%d %d", &n, &m) != EOF)
	{
		memset(first, -1, sizeof(first));
		cnt = 0;
		for(int i = 1; i < n; i++)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			AddEdge(u, v);
		}
		memset(to, 0, sizeof(to));
		int s = BFS(1, 0);
		int t = BFS(s, 1);
		BFS(t, 0);
		pre();
		
		while(m--)
		{
			
			int v, dis;
			scanf("%d %d", &v, &dis);
			//printf("***%d %d %d\n", to[v], d[0][v], d[1][v]);
			if(to[v] < dis)
			{
				puts("0");
				continue;
			}
			if(d[0][v] > d[1][v])
				printf("%d\n", query(0, v, dis));
			else
				printf("%d\n", query(1, v, dis));
		}
	}
	return 0;
}