Binary tree topic -- Luogu p3884 [jloi2009] binary tree problem (DFS for binary tree depth BFS for binary tree width Dijkstra for shortest path)

[JLOI2009] Binary tree problem

Title Description

The depth of a binary tree as shown in the figure below 、 The width and the distance between nodes are ：

• depth ：$4$
• Width ：$4$
• node 8 and 6 Distance between ：$8$
• node 7 and 6 Distance between ：$3$

Where width represents the maximum number of nodes in the same layer on the binary tree .

Give one to 1 Binary tree with node No. as root , Request its depth 、 Width and two specified nodes $x,y$ Distance between .

Input format

The first line is an integer , Represents the number of nodes in a tree $n$.
Next $n-1$ That's ok , Two integers per line $u,v$, Indicates that there is a connection on the tree $u,v$ The edge of .
The last line has two integers $x,y$, Express and seek $x,y$ Distance between .

Output format

Enter three lines , One integer per row , Represent the depth of the binary tree in turn 、 Width and $x,y$ Distance between .

Examples #1

The sample input #1

10                                
1 2                            
1 3                            
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6

Sample output #1

4
4
8

Tips

For all test points , Guarantee $1\le u,v,x,y\le n\le 100$, And what is given is a tree .

The question ：

Give me a With 1 Binary tree with node No. as root , Request its depth 、 Width and two specified nodes x, y Distance between .

Ideas ：

The depth of binary tree is easy to find , direct dfs solve that will do .

about The width of the binary tree , Here is a good idea ：

In the process of wide search , We can Add a... To the queue “0” Mark , As The distinction between extended layers in wide search , It's also The sign of the end of this layer （ The end of the first floor ）.

Let's take an example , Let's suppose that's the case A binary tree ：

At first we were first floor After the root node Add one “0” Mark （ The first layer has only roots ）, about The second floor , When traversal to First floor “0” when , Directly in The second floor Ending Expand into a “0” Mark that will do .

Same thing , When traversing to the second layer “0” when , Directly on the third floor Ending Expand into a “0” Mark .

Get the team leader every time when , If The header value is 0, Then we Judge the number of nodes in the current layer , and Update Max ans.

Final ans That is, the width of the binary tree .

The code snippet is as follows ：

int bfs(int u) // Width   The return value is the width of the binary tree 
{
	int ans = 0;
	vector<int> level;		// Use an auxiliary vector  level  To store all nodes of a certain layer , Its size is used as the width of the updated binary tree  ans  The basis of 
	queue<int> q; q.push(u), q.push(0);	// At first, the root node and  “0”  Mark   Push into the queue 
	while (q.size())
	{
		auto t = q.front(); q.pop();
		if (!t)		// If  t  yes  “0”  Mark , It means that at the end of a certain floor 
		{
			if (level.empty()) break;	// If the current number of stratification points is  0, It indicates that all nodes of the binary tree have been traversed , End the traversal directly 
			ans = max(ans, (int)level.size());		// Otherwise update the answer （ Width of binary tree ）
			q.push(0);	// Expand one at the end of the next layer  “0”  Mark 
			level.clear();	// Clear the current layer , Ready to save the next layer 
			continue;
		}
		level.push_back(t);		// First add the current point 
		if (l[t]) q.push(l[t]);	// Add left son 
		if (r[t]) q.push(r[t]);	// Add your son 
	}
	return ans;
}

Find the distance between two nodes in a given tree , Let's use it directly here Adjacency table to store graph , After use simple dijkstra Solve the shortest path that will do .

Be careful ：

• In the subject , From the binary tree The weight of each edge is 1, The weight of each edge from bottom to top is 2, It seems that there is no mention of .

Code ：

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

using namespace std;
//#define int long long
//#define map unordered_map
const int N = 110, M = (N << 1), inf = 0x3f3f3f3f;
map<int, int> l, r;
int n;
int depth = -1;
int g[N][N];
int dist[N];
bool st[N];

void dfs1(int u, int dep)// depth 
{
    
	if (!l[u] && !r[u])
	{
    
		depth = max(depth, dep);
		return;
	}
	if (l[u]) dfs1(l[u], dep + 1);
	if (r[u]) dfs1(r[u], dep + 1);
}

int bfs(int u) // Width   Because this problem does not require the output of nodes of a certain layer , So we are directly the same  int width  Record the number of nodes in the current layer , And use  width  to update  ans
{
    
	int ans = 0;
	int width = 0;	// There is no need for  vector  了 , It's too much trouble 
	queue<int> q; q.push(u), q.push(0);
	while (q.size())
	{
    
		auto t = q.front(); q.pop();
		if (!t)
		{
    
			if (!width) break;
			ans = max(ans, width);
			q.push(0);
			width = 0;
			continue;
		}
		width++;
		if (l[t]) q.push(l[t]);
		if (r[t]) q.push(r[t]);
	}
	return ans;
}

int dijk(int a, int b)
{
    
	memset(dist, 0x3f, sizeof dist);
	memset(st, false, sizeof st);
	dist[a] = 0;
	for (int i = 0; i < n; ++i)
	{
    
		int t = -1;
		for (int j = 1; j <= n; ++j)
		{
    
			if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
		}
		st[t] = true;
		for (int j = 1; j <= n; ++j)
		{
    
			dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
	}
	return dist[b];
}

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

	while (T--)
	{
    
		memset(g, 0x3f, sizeof g);
		cin >> n;
		for (int i = 0; i < n - 1; ++i)
		{
    
			int x, y; cin >> x >> y;
			if (!l[x]) l[x] = y;
			else if (!r[x]) r[x] = y;
			g[x][y] = min(g[x][y], 1);
			g[y][x] = min(g[y][x], 2);
		}
		dfs1(1, 1);
		cout << depth << '\n';
		cout << bfs(1) << '\n';
		int a, b; cin >> a >> b;
		cout << dijk(a, b) << '\n';
	}

	return 0;
}