一棵 nn 个点的树，点权最初为 1∼n1 \sim n 的排列。

定义一个删点过程: 每次找到权值最小的叶子,删去它以及连接的边，重复这个过程直到剩下一个点，然后删去最后的点。

处理 qq 个询问:

  • 将一个点xx 的权值赋为当前最大权值 +1+1
  • 查询在删点过程中，xx 会是第几个被删除的

n,q≤2∗105n, q \le 2 *10^5

CF 1137F

Solution

观察到删除序列的一些性质:

  • 权值最大的点最后一个被删。
  • 权值最大的点为xx，次大的为 yy，那么序列最后一段就是 yy 到 xx 的简单路径。

不难分析，一次赋值操作，不会影响非 y→xy \rightarrow x 路径上的点的变叶子过程

所以造成的影响就是将 y→xy \rightarrow x 路径提到序列最后，其他点的顺序不变

考虑用LCT来维护这个过程，强制每次LCT的根结点都是当前全局权值最大的节点

具体实现上，LCT维护每条实链上的所有点权值相同；用一个树状数组（下标为权值，值为这个权值的点数）来维护一个关于权值的前缀和

修改操作就是LCT的make_root

查询就是所有权值小于它的点数，加上它在LCT上的右子树大小

有一点点小细节。。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 2e5 + 100;

int N, Q, M, color_cnt;
int e, Begin[Maxn], To[Maxn << 1], Next[Maxn << 1];

namespace BIT
{
#define lowbit(x) (x & (-x))
	int sum[Maxn << 1];
	inline void add (int x, int val) { for (; x <= M; x += lowbit(x)) sum[x] += val; }
	inline int query (int x) { int ans = 0; for (; x; x -= lowbit(x)) ans += sum[x]; return ans; }
}

namespace LCT
{
#define fa(x) (node[x].fa)
#define ls(x) (node[x].ch[0])
#define rs(x) (node[x].ch[1])

	struct info
	{
		int fa, ch[2], size, rev, col, tag;
	} node[Maxn];

	inline int is_root (int x) { return ls (fa (x)) != x && rs (fa (x)) != x; }

	inline int judge_dir (int x) { return rs (fa (x)) == x; }

	inline void connect (int x, int f, int dir) { node[f].ch[dir] = x, fa (x) = f; }

	inline void push_up (int root) { node[root].size = node[ls (root)].size + node[rs (root)].size + 1; }

	inline void push_down (int x)
	{
		if (node[x].rev)
		{
			swap (ls (x), rs (x));
			node[ls (x)].rev ^= 1, node[rs (x)].rev ^= 1;
			node[x].rev = 0;
		}
		if (node[x].tag)
		{
			node[ls (x)].tag = node[ls (x)].col = node[x].tag;
			node[rs (x)].tag = node[rs (x)].col = node[x].tag;
			node[x].tag = 0;
		}
	}

	inline void build (int x, int f)
	{
		fa (x) = f, node[x].col = x;

		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (y == f) continue ;
			build (y, x);
			if (Chkmax (node[x].col, node[y].col)) rs (x) = y;
		}

		push_up (x), BIT :: add (node[x].col, 1);
	}

	inline void rotate (int x)
	{
		int f = fa (x), anc = fa (f), dir_x = judge_dir (x), dir_f = judge_dir (f);
		if (!is_root (f)) node[anc].ch[dir_f] = x; fa (x) = anc;
		connect (node[x].ch[dir_x ^ 1], f, dir_x);
		connect (f, x, dir_x ^ 1);
		push_up (f), push_up (x);
	}

	inline void splay (int x)
	{
		static int Stack[Maxn], top;
		Stack[top = 1] = x;
		for (int y = x; !is_root (y); y = fa (y)) Stack[++top] = fa (y);
		while (top) push_down (Stack[top--]);

		for (; !is_root (x); rotate (x))
			if (!is_root (fa (x)))
				rotate (judge_dir (x) == judge_dir (fa (x)) ? fa (x) : x);
	}

	inline void access (int x, int col)
	{
		for (int y = 0; x; y = x, x = fa (x))
		{
			splay (x);
			BIT :: add (node[x].col, - (node[ls (x)].size + 1));
			BIT :: add (col, node[ls (x)].size + 1);
			rs (x) = y, push_up (x);
		}
	}

	inline void make_root (int x, int col)
	{
		access (x, col), splay (x);
		node[x].tag = node[x].col = col;
		node[x].rev ^= 1;
	}

	inline int query (int x) { splay (x); return BIT :: query (node[x].col - 1) + node[rs (x)].size + 1; }

#undef fa
#undef ls
#undef rs
}

inline void add_edge (int x, int y) { To[++e] = y, Next[e] = Begin[x], Begin[x] = e; }

inline void Solve ()
{
	LCT :: build (N, 0);

	while (Q--)
	{
		char S[10]; scanf("%s", S); int x = read<int>();
		if (S[0] == 'u') LCT :: make_root (x, ++color_cnt);
		else if (S[0] == 'w') printf("%d\n", LCT :: query (x));
		else
		{
			int y = read<int>();
			printf("%d\n", LCT :: query (x) < LCT :: query (y) ? x : y);
		}
	}
}

inline void Input ()
{
	N = color_cnt = read<int>(), Q = read<int>(), M = N + Q + 1;
	for (int i = 1; i < N; ++i)
	{
		int x = read<int>(), y = read<int>();
		add_edge (x, y), add_edge (y, x);
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}