调了一下午了还是 6 分。。。
查看原帖
调了一下午了还是 6 分。。。
677091
MnZnOIer楼主2024/8/5 17:04

本人已死,有事烧纸。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5;
int n, k, deep[N], siz[N], top[N], son[N], fa[N], id[N], h[N], c, tree[N << 2], tag[N << 2];
struct Edge{int v, nxt;}e[N << 1];
void add (int from, int to)
{
	e[++ c].nxt = h[from];
	h[from] = c;
	e[c].v = to;
}
void dfs1 (int d, int fath)
{
	siz[d] = 1;
	fa[d] = fath;
	deep[d] = deep[fath] + 1;
	for (int i = h[d]; i; i = e[i].nxt)
	{
		int y = e[i].v;
		if (y == fath)continue;
		dfs1 (y, d);
		siz[d] += siz[y];
		if (! son[d] || siz[son[d]] < siz[y])son[d] = y;
	}
}
void dfs2 (int d, int topx)
{
	id[d] = ++ c;
	top[d] = topx;
	if (! son[d])return;
	dfs2 (son[d], topx);
	for (int i = h[d]; i; i = e[i].nxt)
	{
		int y = e[i].v;
		if (y != fa[d] && y != son[d])dfs2 (y, y);
	}
}
int ls (int x){return x << 1;}
int rs (int x){return x << 1 | 1;}
void addtag (int x, int l, int r)
{
	tree[x] += r - l + 1;
	++ tag[x];
}
void push_up (int x){tree[x] = max (tree[ls (x)], tree[rs (x)]);}
void push_down (int x, int l, int r)
{
	if (tag[x])
	{
		int mid = (l + r) >> 1;
		addtag (ls (x), l, mid);
		addtag (rs (x), mid + 1, r);
		tag[x] = 0;
	}
}
void update (int x, int l, int r, int L, int R)
{
	if (L <= l && r <= R)
	{
		addtag (x, l, r);
		return;
	}
	push_down (x, l, r);
	int mid = (l + r) >> 1;
	if (L <= mid)update (ls (x), l, mid, L, R);
	if (R > mid)update (rs (x), mid + 1, r, L, R);
	push_up (x);
}
void up (int x, int l, int r)
{
	if (l == r)return;
	push_down (x, l, r);
	int mid = (l + r) >> 1;
	up (ls (x), l, mid);
	up (rs (x), mid + 1, r);
	push_up (x);
}
signed main ()
{
	ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
//	freopen ("P3128_2.in", "r", stdin); 
	cin >> n >> k;
	for (int i = 1; i < n; ++ i)
	{
		int a, b;
		cin >> a >> b;
		add (a, b), add (b, a);
	}
	c = 0;
	dfs1 (1, 0);
	dfs2 (1, 1);
	while (k --)
	{
		int x, y;
		cin >> x >> y;
		while (top[x] != top[y])
		{
			if (deep[top[x]] < deep[top[y]])swap (x, y);
			update (1, 1, n, id[top[x]], id[x]);
			x = fa[top[x]];
		}
		if (deep[x] > deep[y])swap (x, y);
		update (1, 1, n, id[x], id[y]);
	}
	up (1, 1, n);
	cout << tree[1];
	return 0;
}
2024/8/5 17:04
加载中...