有nn棵树，一开始都只有一个节点，标号为1。每棵树都有一个生长节点，有生长出子节点的能力。你需要支持以下mm个操作：

  • 0 l r ：将第 ll 棵树到第 rr 棵树的生长节点下面长出一个子节点，子节点的标号为上一个00号操作叶子标号加11，ll 到 rr 之间的树长出的节点标号都相同。
  • 1 l r x：将第 ll 棵树到第 rr 棵树的生长节点改到标号为 xx 的节点。对于 i∈[l,r]i\in [l,r] 这棵树，如果标号xx的点不在其中，那么这个操作对该树不产生影响。
  • 2 x u v：询问第 xx 棵树中节点 uu 到节点 vv 点的距离。保证这棵树中节点 uu 和节点 vv 存在。

n≤105,m≤3∗105n\le 10^5, m\le 3 * 10^5

Luogu P3348

Solution

因为题目保证询问的节点存在，所以对于每一棵树，我们都可以把它先操作完再询问。

考虑离线，按树的编号做扫描线，即先把第一棵树的形态全都建出来，回答询问，然后把它变化到第二棵树的形态……以此类推

那么现在就需要考虑如何从某一棵树变化到下一棵树

不难发现，更换生长节点的实质就是更换某些节点的父亲：在ll处将当前生成节点及其包含的节点全部移植到它更改后的位置，再在r+1r+1处移植回来

为了方便进行这个操作，我们在每个生长节点下新建一个虚点（虚点权值为00，实点权值为11），把接下来需要生长出的节点都接在这个虚点的下方，那么每次只需要更换虚点的父亲即可

形象地理解以下，一开始形成的是一棵这样的东西：

19-1-3-1

就是一条虚点构成的链，上面带了许多实点

每次操作就是把某个虚点切断它与父亲的边，再连到某个实点上

最后考虑一下如何计算两点距离

因为这道题树是有根的，LCT不能make_root，因此不能split算答案

那么直接用sum[x]+sum[y]−2∗sum[lca]sum[x]+sum[y]-2*sum[lca]即可

对于求 lcalca ，先 access(y) ，再在access(x)的时候得到的最后一个跳虚边的点即是它们的 lcalca

具体码的时候要注意因为没有make_root，某些细节稍微有改变

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
#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; }

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

template <typename T> 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;
}

const int Maxn = 5e5 + 100;

int N, M, Q;

int node_cnt, id[Maxn], real_num;
struct tree
{
	int fa, ch[2], rev, sum, val;
} Tree[Maxn];

namespace LCT
{
#define ls (Tree[x].ch[0])
#define rs (Tree[x].ch[1])
	int Stack[Maxn], top;

	inline int is_root (int x) { return Tree[Tree[x].fa].ch[0] != x && Tree[Tree[x].fa].ch[1] != x; }
	inline int judge (int x) { return Tree[Tree[x].fa].ch[1] == x; }
	inline void connect (int x, int f, int dir) { Tree[x].fa = f; Tree[f].ch[dir] = x; } 
	inline void push_up (int x) { Tree[x].sum = Tree[ls].sum + Tree[rs].sum + Tree[x].val; }
	inline void push_down (int x) { if (Tree[x].rev) swap(ls, rs), Tree[ls].rev ^= 1, Tree[rs].rev ^= 1, Tree[x].rev = 0; } 
	inline void rotate (int x) 
	{
		int f = Tree[x].fa, anc = Tree[f].fa, dirx = judge (x), dirf = judge (f);
		if (!is_root(f)) Tree[anc].ch[dirf] = x; Tree[x].fa = anc;
		connect (Tree[x].ch[dirx ^ 1], f, dirx);
		connect (f, x, dirx ^ 1);
		push_up(f), push_up(x);
	}
	inline void splay (int x) 
	{ 
		Stack[++top] = x; for (int y = x; !is_root(y); y = Tree[y].fa) Stack[++top] = Tree[y].fa;
		while (top) push_down(Stack[top--]);
		for (; !is_root(x); rotate (x)) if (!is_root(Tree[x].fa)) rotate (judge(x) == judge(Tree[x].fa) ? Tree[x].fa : x);
	}

	inline int access (int x) { int y = 0; for (; x; x = Tree[y = x].fa) splay(x), rs = y, push_up(x); return y; }
	inline void link (int x, int f) { splay(x); Tree[x].fa = f; }
	inline void cut (int x) 
	{ 
		access(x), splay (x); 
/**/	Tree[ls].fa = 0, ls = 0; /*not Tree[ls].fa = ls = 0;*/
		push_up(x); 
	}
	inline void newnode (int f, int val) 
	{ 
/**/	++node_cnt; Tree[node_cnt].val = Tree[node_cnt].sum = val; 
        /*not Tree[++node_cnt].val = Tree[node_cnt].sum = val;*/
		link (node_cnt, f); 
		if (val) id[++real_num] = node_cnt; 
	}
	inline int query (int x, int y) 
	{ 
		int ans = 0;
		access (x), splay(x), ans += Tree[x].sum;
		int lca = access(y); splay(y), ans += Tree[y].sum;
		access(lca), splay(lca), ans -= Tree[lca].sum * 2;
		return ans;
	}

#undef ls
#undef rs
}

struct query { int pos, time, x, y, op; } Query[Maxn];

inline int cmp (query a, query b)
{
	if (a.pos == b.pos) { if (a.op == b.op) return a.time < b.time; return a.op < b.op; }
	return a.pos < b.pos;
}

int L[Maxn], R[Maxn], Ans[Maxn];

inline void Solve ()
{
	LCT :: newnode(0, 1), LCT :: newnode(1, 0);
	L[real_num] = 1, R[real_num] = N;
	int last = 2, op_cnt = 0;

	for (int i = 1; i <= M; ++i)
	{
		int op = read<int>();
		if (!op)
		{
			LCT :: newnode (last, 1);
			L[real_num] = read<int>(), R[real_num] = read<int>();
		}
		else if (op == 1)
		{
			int l = read<int>(), r = read<int>(), x = read<int>();
			Chkmax(l, L[x]), Chkmin(r, R[x]);
			if (l > r) continue;
			LCT :: newnode (last, 0);
			Query[++op_cnt] = (query){l, i, node_cnt, id[x], op};
			Query[++op_cnt] = (query){r + 1, i, node_cnt, last, op};
			last = node_cnt;
		}
		else
		{
			int x = read<int>(), u = read<int>(), v = read<int>();
			Query[++op_cnt] = (query){x, ++Q, id[u], id[v], op};
		}
	}
	
	sort (Query + 1, Query + op_cnt + 1, cmp);

	for (int i = 1; i <= op_cnt; ++i)
	{
		if (Query[i].op == 1) LCT :: cut(Query[i].x), LCT :: link (Query[i].x, Query[i].y);
		else Ans[Query[i].time] = LCT :: query (Query[i].x, Query[i].y);
	}

	for (int i = 1; i <= Q; ++i) printf("%d\n", Ans[i]);
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}

Debug

一个超级坑的点。。。

  • 73L和78L本质错的地方是一样的，具体见Debug