Reading

CodeForces 1137F Matches Are Not a Child's Play

Fanyi Pu

题目大意

我们定义一棵树的删除序列为：每一次将树中编号最小的叶子删掉，将该节点编号加入到当前序列的最末端，最后只剩下一个节点时将该节点的编号加入到结尾。

例如对于上图中的树，它的删除序列为：2 4 3 1 5。

现在给出一棵 n 个节点的树，有 m 次操作：

  1. up v：将 v 号节点的编号变为当前所有节点编号的 max+1；
  2. when v：查询 v 在当前树的删除序列中是第几号元素；
  3. compare u v：查询 u 和 v 在当前树的删除序列中谁更靠前。

输入格式

第一行两个正整数 n,q(1≤n,q≤200000) 表示树的点数和操作数。

接下来 n−1 行每行 2 个正整数 u,v(1≤u,v≤n) 表示树上的一条边。

接下来 q 行每行描述一个操作。

输出格式

每一个询问输出一行。

对于 when v 询问，输出一个正整数表示 v 是当前删除序列的哪一个元素。

对于 compare u v 询问，如果 u 在删除序列中更靠前则输出 u，否则输出 v。1

题解

显然在任意时刻最大的那个节点一定是在最后被删的。

于是我们考虑 up 操作带来的影响。

假设 up 了 x，上一次（up 前）最大的那个点是 y。

我们发现最后删着删着一定只剩下了 x 到 y 路径上的这几个点。

然后从 y 开始一个一个往 x 那边删。

于是 y∼x 这条链上的点移到了删除序列的末尾。

我们可以把 y∼x 看成一个缩起来的点，我们发现其它点的相对位置不变。

接下来的思路感觉跟这题很像。

我们考虑用 LCT 维护这棵树，LCT 中的每棵 splay 表示一段连续的删除区间。

开始时根当然是最大的。

样例大概是这样一幅图：

删除序列应该是 2 4 3 1 5。

根当然就是最大的那个点。

由于一个 splay 是连续删的。所以我们给每个 splay 一个标号（具体到实现就是给 splay 上每个点染色，可以参考下面的代码），把它放在树状数组上，即在该 splay 的 color 上加上该 splay 的 size。

cpp
inline void dfs(int now)
{
	col[now] = now, siz[now] = 1;
	for(int i = first[now]; i; i = e[i].nxt)
	{
		register int to = e[i].to;
		if(to != fa[now])
		{
			fa[to] = now; dfs(to);
			if(col[to] > col[now]) // 如果它后代有比它大的节点，那么一定会影响他它
			{
				col[now] = col[to];
				s[now][1] = to;
				siz[now] = siz[to] + 1;
			}
		}
	}
	tr.add(col[now], 1); // 树状数组在该color上加1
}

我们考虑查询，就是该点所在 splay 之前的所有点数加上该 splay 上所有该结点后面的点数。

大概就是 树状数组.query(col[x] - 1) + splay.query(在x之前的节点个数)。

当然也可以写成：

cpp
inline int query(int x)
{
	splay(x);
	return tr.query(col[x]) - siz[s[x][0]];
}

最后考虑修改。

我们发现修改就是 make_root，当然因为 make_root 里已经有 access 了。

至于轻重链切换的时候，只要在树状数组里把原有的 splay 删掉，新增的 splay 加上就可以了，具体可以见代码。

cpp
inline void access(int x)
{
	for(int y = 0; x; x = fa[y = x])
	{
		splay(x);
		s[x][1] = 0; // 假装它右边什么都没有，这样就可以把需要新增的splay整个提取出来了
		push_up(x);
		tr.add(col[x], -siz[x]);
		tr.add(nowcol, siz[x]);
		s[x][1] = y; // 然后在接上y
		push_up(x);
	}
}

inline void make_root(int x)
{
	nowcol++;
	access(x);
	splay(x);
	fan(x); // 翻转
	col[x] = nowcol; // 最后再把整个splay的color标记打上
}

代码

cpp
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 200005;
const int maxq = 200005;

int n, q;

struct Edge
{
	int to, nxt;
} e[maxn << 1];

int first[maxn];

inline void add_edge(int from, int to)
{
	static int cnt = 0;
	e[++cnt].nxt = first[from];
	e[cnt].to = to;
	first[from] = cnt;
	e[++cnt].nxt = first[to];
	e[cnt].to = from;
	first[to] = cnt;
}

#define lowbit(x) (x & -x)

struct BIT
{
	int xx[maxn << 1];

	inline void add(int pla, int x)
	{
		for(; pla <= n + q; pla += lowbit(pla))
			xx[pla] += x;
	}

	inline int query(int pla)
	{
		int ans = 0;
		for(; pla; pla -= lowbit(pla))
			ans += xx[pla];
		return ans;
	}
} tr;

int fa[maxn];
int s[maxn][2];
int siz[maxn];
int col[maxn];
int lzy[maxn];

inline void dfs(int now)
{
	col[now] = now;
	siz[now] = 1;
	for(int i = first[now]; i; i = e[i].nxt)
	{
		register int to = e[i].to;
		if(to != fa[now])
		{
			fa[to] = now;
			dfs(to);
			if(col[to] > col[now])
			{
				col[now] = col[to];
				s[now][1] = to;
				siz[now] = siz[to] + 1;
			}
		}
	}
	tr.add(col[now], 1);
}

inline bool nroot(int x)
{
	return s[fa[x]][0] == x || s[fa[x]][1] == x;
}

inline void push_up(int x)
{
	siz[x] = siz[s[x][0]] + siz[s[x][1]] + 1;
}

inline void fan(int x)
{
	lzy[x] ^= 1;
	swap(s[x][0], s[x][1]);
}

inline void push_down(int x)
{
	if(lzy[x])
	{
		lzy[x] = 0;
		if(s[x][0])
			fan(s[x][0]);
		if(s[x][1])
			fan(s[x][1]);
	}
	if(s[x][0])
		col[s[x][0]] = col[x];
	if(s[x][1])
		col[s[x][1]] = col[x];
}

inline void rotate(int x)
{
	int y = fa[x], z = fa[y];
	int d = s[y][1] == x, k = s[x][!d];
	if(nroot(y))
		s[z][s[z][1] == y] = x;
	fa[x] = z;
	s[x][!d] = y;
	fa[y] = x;
	s[y][d] = k;
	if(k)
		fa[k] = y;
	push_up(y);
	push_up(x);
}

int sta[maxn];

inline void splay(int x)
{
	int tx = x;
	int top = 0;
	sta[++top] = tx;
	while(nroot(tx))
		sta[++top] = (tx = fa[tx]);
	while(top)
		push_down(sta[top--]);
	while(nroot(x))
	{
		register int y = fa[x];
		if(nroot(y))
		{
			register int z = fa[y];
			rotate(((s[z][1] == y) ^ (s[y][1] == x)) ? x : y);
		}
		rotate(x);
	}
}

int nowcol;

inline void access(int x)
{
	for(int y = 0; x; x = fa[y = x])
	{
		splay(x);
		s[x][1] = 0;
		push_up(x);
		tr.add(col[x], -siz[x]);
		tr.add(nowcol, siz[x]);
		s[x][1] = y;
		push_up(x);
	}
}

inline void make_root(int x)
{
	nowcol++;
	access(x);
	splay(x);
	fan(x);
	col[x] = nowcol;
}

char opt[23];

inline int query(int x)
{
	splay(x);
	return tr.query(col[x]) - siz[s[x][0]];
}

int main()
{
	scanf("%d%d", &n, &q);
	nowcol = n;
	for(int i = 1, f, t; i < n; ++i)
	{
		scanf("%d%d", &f, &t);
		add_edge(f, t);
	}
	dfs(n);
	int _u, _v;
	for(int i = 1; i <= q; ++i)
	{
		scanf("%s", opt);
		if(opt[0] == 'u')
		{
			scanf("%d", &_v);
			make_root(_v);
		}
		else if(opt[0] == 'w')
		{
			scanf("%d", &_v);
			printf("%d\n", query(_v));
		}
		else
		{
			scanf("%d%d", &_u, &_v);
			int ans1 = query(_u);
			int ans2 = query(_v);
			printf("%d\n", ans1 < ans2 ? _u : _v);
		}
	}
	return 0;
}

Footnotes

  1. 翻译来自luogu ↩

Cite this post

@misc{pu2019oiicpccodeforcescf1137f,
  author = {Pu, Fanyi},
  title  = {CodeForces 1137F Matches Are Not a Child's Play},
  year   = {2019},
  month  = {3},
  url    = {https://pufanyi.com/blog/oi-icpc/codeforces/cf1137f}
}