Luogu p4281 [ahoi2008] emergency gathering / gathering (tree doubling LCA)

[AHOI2008] Emergency assembly / party

Title Description

There is a very fun game on happy island , be called “ Emergency assembly ”. Scattered on the island $n$ A waiting point , Yes $n-1$ A road connects them , Each road connects two waiting points , And you can walk through all the waiting points through these roads , It costs a game coin to go from one point to another through the road .

The players are in groups of three , At the beginning , All personnel are randomly dispersed at each waiting point （ Each point allows multiple people to wait at the same time ）, Everyone has enough game coins （ Used to pay for the cost of using roads ）、 Map （ Indicate the road connection between waiting points ） And to the phone （ Used to contact members of the same group ）. When the set number blows , Get in touch quickly with each group , After knowing the waiting point of all members of your group , Quickly in $n$ Determine a staging point among the waiting points , All members of the group will assemble at this assembly point , The least expensive group used in the collection will be the winner of the game .

Little coco and his friends invite you to join this game , It's up to you to choose the assembly point , Smart you can accomplish this task , Help little coco win the game ？

Input format

Two positive integers in the first line $n$ and $m$, Respectively represents the number of waiting points （ Waiting point also starts from $1$ To $n$ Number ） And the number of times it takes to complete the collection to win the prize .

And then $n-1$ That's ok , Two positive integers per line $a,b$, Indicates that the number is $a$ And the number is $b$ There is a way between the waiting points .

And then $m$ That's ok , Use three positive integers per line $x,y,z$, It means little cocoa before a set 、 Little cocoa's friend and the number of your waiting point .

Output format

The output, $m$ That's ok , Two integers separated by spaces on each line $p,c$. Among them the first $i$ Line representation $i$ The secondary assembly point is selected under the number $p$ Waiting point for , The total cost of the collection is $c$ A game coin .

Examples #1

The sample input #1

6 4  
1 2  
2 3  
2 4 
4 5
5 6
4 5 6
6 3 1
2 4 4 
6 6 6

Sample output #1

5 2
2 5
4 1
6 0

Tips

about $40\%$ The data of ,$n\le 2\times 10^3$,$m\le 2\times 10^3$.

about $100\%$ The data of ,$1\le x,y,z\le n\le 5\times 10^5$,$1\le m\le 5\times 10^5$.

The question ：

Given n A little bit , common n - 1 There is a root tree on the edge , as well as m Time to ask , Give out... Every time you ask 3 A little bit , Ask in the tree Find a little , bring 3 The sum of the distances from a point to that point is the smallest , Output The number of the point and the sum of the distances .

Ideas ：

If it's not a label , I may not think of using LCA To do it .

Next, go straight to the idea .

Let's simulate the sample on paper , We can find out ：

• When a、b、c Two of the three points lca When it is the same point （ coincidence ）, Then the point we choose is the one between the other point and any of these two points lca, for instance , If a、b Of lca Are all d, Then the point we want to choose is c、d Of lca.
• When a、b、c Three dots lca Each are not identical perhaps All the same , that The point we choose That is to say At any two points lca.

I simulated it on paper and found that it was not easy , This finding can be remembered as a conclusion .

The remaining steps , Just calculate the distance according to the situation and output it .

Code ：

set On the tree lca Just a board , Note that this topic is obviously Online lca It is more convenient , It doesn't seem to work tarjan seek lca

Always at first TLE stay 8、9, The reason lies in ： There is no need to open one The length is 5e5 Of cnt Array To express 3 Point lca Coincidence , This leads to such a large array for each query With O(n) Empty your time , Obviously T.（ Accumulate experience , Don't do it again ）

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
//#define map unordered_map
const int N = 5e5 + 10, M = N << 1;
int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][20];
int dist[N];

void add(int a, int b)
{
    
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int father)
{
    
	for (int i = h[u]; ~i; i = ne[i])
	{
    
		int j = e[i];
		if (j == father) continue;
		dist[j] = dist[u] + 1;
		dfs(j, u);
	}
}

void bfs(int root)
{
    
	queue<int> q; q.push(root);
	while (q.size())
	{
    
		auto t = q.front(); q.pop();
		for (int i = h[t]; ~i; i = ne[i])
		{
    
			int j = e[i];
			if (depth[j] > depth[t] + 1)
			{
    
				depth[j] = depth[t] + 1;
				fa[j][0] = t;
				for (int k = 1; k <= 19; ++k)
				{
    
					fa[j][k] = fa[fa[j][k - 1]][k - 1];
				}
				q.push(j);
			}
		}
	}
}

void init(int root)
{
    
	memset(depth, 0x3f, sizeof depth);
	depth[0] = 0, depth[root] = 1;
	bfs(root);
}

int lca(int x, int y)
{
    
	if (depth[x] < depth[y])
	{
    
		swap(x, y);
	}
	for (int k = 19; k >= 0; --k)
	{
    
		if (depth[fa[x][k]] >= depth[y]) x = fa[x][k];
	}

	if (x == y) return x;
	for (int k = 19; k >= 0; --k)
	{
    
		if (fa[x][k] != fa[y][k])
		{
    
			x = fa[x][k];
			y = fa[y][k];
		}
	}
	return fa[x][0];
}

int getdis(int a, int b)
{
    
	return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}

signed main()
{
    
	int T = 1; //cin >> T;

	while (T--)
	{
    
		scanf("%d%d", &n, &m);
		memset(h, -1, sizeof h);
		int t = n - 1, root = 0;
		for (int i = 0; i < t; ++i)
		{
    
			int a, b; scanf("%d%d", &a, &b);
			if (!i) root = a;
			add(a, b), add(b, a);
		}
		init(root);
		dfs(root, -1);
		while (m--)
		{
    
			int x, y, z; scanf("%d%d%d", &x, &y, &z);

			int p1 = lca(x, y);
			int p2 = lca(y, z);
			int p3 = lca(x, z);
			int res = 0;
			int point = 0;
			
			if (p1 == p2 && p1 != p3)
			{
    
				int d1 = getdis(x, p3);
				int d2 = getdis(y, p3);
				int d3 = getdis(z, p3);
				res = d1 + d2 + d3;
				point = p3;
			}
			else if (p1 == p3 && p1 != p2)
			{
    
				int d1 = getdis(x, p2);
				int d2 = getdis(y, p2);
				int d3 = getdis(z, p2);
				res = d1 + d2 + d3;
				point = p2;
			}
			else if(p2 == p3 && p2 != p1)
			{
    
				int d1 = getdis(x, p1);
				int d2 = getdis(y, p1);
				int d3 = getdis(z, p1);
				res = d1 + d2 + d3;
				point = p1;
			}
			else
			{
    
				res = getdis(x, p1) + getdis(y, p1) + getdis(z, p1);
				point = p1;
			}
			printf("%d %d\n", point, res);
		}
	}

	return 0;
}