寒假19 数据结构-树的一点点

#include<iostream>
using namespace std;
#include<vector>
int n, m;
int const N = 1e5 + 5;
vector<int>vt[N];
bool vis[N];
int ans = 0;
void dfs(int a, int b)
{
	for (vector<int>::iterator it = vt[a].begin();it != vt[a].end();it++)
	{
		if (!vis[*it])
		{
			ans++;
			vis[*it] = true;
		}
		if (b + 1 <= m)
		{
			dfs(*it, b + 1);
		}
	}
}
int main()
{
	cin >> n >> m;
	int a, b;
	vis[1] = 1;
	for (int i = 1;i <= n - 1;i++)
	{
		cin >> a >> b;
		vt[a].push_back(b);
		vt[b].push_back(a);
	}
	dfs(1, 1);
	cout << ans << endl;
	return 0;
}

#include<iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 10;
int n, m, s;
vector<int> e[N];
int fa[N], depth[N];
int dp[N][20]; //dp[i][j]表示i节点的第2^j次方父亲，如：dp[i][0]表示i的直接父亲，dp[i][1]表示爷爷(2^1 = 2)
// dfs(u, d, f)：u节点的深度为d，直接父亲是f，并记录
void dfs(int u, int d, int f)
{
	fa[u] = f, depth[u] = d;
	for (auto v : e[u])
	{
		if (v != f)
		{
			dfs(v, d + 1, u);
		}
	}
}
// dfs_(u, d, f)：u节点的深度为d，直接父亲是f，并更新dp数组
void dfs_(int u, int d, int f)
{
	fa[u] = f, depth[u] = d;
	dp[u][0] = f;
	for (int i = 1; i < 20; i++)
	{
		dp[u][i] = dp[dp[u][i - 1]][i - 1];
	}
	for (auto v : e[u])
	{
		if (v != f)
		{
			dfs_(v, d + 1, u);
		}
	}
}
int lca(int u, int v)
{
	if (depth[u] < depth[v]) swap(u, v); //确保u的深度更深
	while (depth[u] > depth[v]) u = fa[u]; //更新u为u的父亲，使得u和v的深度一致
	while (u != v) u = fa[u], v = fa[v]; //一直往上跳，直到找到lca
	return u;
}
int lca_(int u, int v)
{
	if (u == v)return u;
	if (depth[u] < depth[v]) swap(u, v); //确保u的深度更深
	for (int i = 19; i >= 0; i--)
	{
		if (depth[dp[u][i]] >= depth[v])
		{
			u = dp[u][i];
		}
	}
	if (u == v)return u;
	for (int i = 19;i >= 0;i--)
	{
		if (dp[u][i] != dp[v][i])
		{
			u = dp[u][i];
			v = dp[v][i];
		}
		//cout << i << " " << u << " " << v << endl;
	}
	return fa[u];
}
int main()
{
	cin >> n >> m >> s;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		e[u].push_back(v), e[v].push_back(u);
	}
	dfs_(s, 1, 0);
	
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		cout << lca_(a, b) << endl;
	}
	return 0;
}

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
int n, m, s;
int const N = 5e5 + 10;
int fa[N];
int depth[N];
vector<int>vt[N];
int dp[N][20];
void dfs(int a, int b)
{
	for (int i = 0;i < 20;i++)
	{
		if (i == 0)
		{
			dp[a][i] = fa[a];
		}
		else
		{
			dp[a][i] = dp[dp[a][i - 1]][i - 1];
		}
	}
	for (vector<int>::iterator it = vt[a].begin();it != vt[a].end();it++)
	{
		if ((*it) != fa[a])
		{
			depth[*it] = b;
			fa[*it] = a;
			dfs(*it, b + 1);
		}
	}
}

int lca(int u, int v)
{
	if (u == v)
	{
		return u;
	}
	if (depth[u] < depth[v])swap(u, v);
	int du = depth[u];
	int dv = depth[v];
	for (int i = 19;i >= 0;i--)
	{
		if (depth[dp[u][i]] >= dv)
		{
			//cout << depth[dp[u][i]] << " dv=" << dv << endl;
			u = dp[u][i];
		}
	}
	if (u == v)
	{
		return u;
	}
	for (int i = 19;i >= 0;i--)
	{
		if (dp[u][i] != dp[v][i])
		{
			u = dp[u][i];
			v = dp[v][i];
		}
	}
	//cout << "u=" << u << " v=" << v << endl;
	return fa[u];
}
int main()
{
	cin >> n >> m >> s;
	for (int i = 1;i < n;i++)
	{
		int a, b;
		cin >> a >> b;
		vt[a].push_back(b);
		vt[b].push_back(a);
	}
	depth[s] = 1;
	dfs(s, 2);
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		cout << lca(a, b) << endl;
	}
	return 0;
}