只有6分,什么情况
查看原帖
只有6分,什么情况
1140371
ruanertanjing楼主2024/5/22 01:35


#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int N = 5e4 + 5;
const int M = N - 1;

int cnt;
int head[N];
int fa[N][20];
int deepth[N];
int power[N];
int ans;

struct EDGE
{
	int v;
	int next;
}EDGE[M * 2];

void add(int u, int v/*, int w*/)
{
	cnt++;=
	EDGE[cnt].v = v;
	EDGE[cnt].next = head[u];
	head[u] = cnt;
}

void dfs(int son, int father)
{
	fa[son][0] = father;
	deepth[son] = deepth[father] + 1;
	for (int i = 1; (1 << i) <= deepth[son]; i++)
		fa[son][i] = fa[fa[son][i - 1]][i -1];
	for (int i = head[son]; i; i = EDGE[i].next)
	{
		int v = EDGE[i].v;
		if (v != father)/**/
			dfs(v, son);
	}
}

int lca(int x, int y)
{
	if (deepth[x] < deepth[y])
		swap(x, y);

	//使得x,y位于同一高度
	for (int i = 20; i >= 0; i--)
	{
		if (deepth[fa[x][i]] >= deepth[y])
			x = fa[x][i];
	}
	if (x == y)
		return x;
	//使得x,y位于公共祖先的下一层
	for (int i = 20; i > 0; i--)
	{
		if (fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

void getans(int son, int father)
{
	for (int i = head[son]; i; i = EDGE[i].next)
	{
		if (EDGE[i].v == father)/**/
			continue;
		
		getans(EDGE[i].v, son);
		power[son] += power[EDGE[i].v];
	}
	ans = max(ans, power[son]);
}

void solve()
{
	int n, k;
	cin >> n >> k;
	int u, v, w;

	//建树
	for (int i = 0; i < n - 1; i++)
	{
		cin >> u >> v;
		add(u, v);
		add(v, u);
//		fa[v] = u;
	}
	dfs(1, 0);//求第2 ^ n个父亲

	//求公共祖先、书上差分
	for (int i = 0; i < k; i++)
	{
		cin >> u >> v;
		//add(u, v, 1);
		int togetherfather = lca(u, v);
		power[u]++;
		power[v]++;
		power[togetherfather]--;
		power[fa[togetherfather][0]]--;
	}
	getans(1, 0);
	cout << ans << endl;
}

int main()
{
	solve();
	return 0;
}
2024/5/22 01:35
加载中...