自动搬运

查看原文

来自洛谷，原作者为

	ningago 恋爱脑

搬运于2025-08-24 22:56:43，当前版本为作者最后更新于2025-01-09 21:51:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以当作 LCT 维护动态基环树的模板。

为了保证了每个点都一定有恰好一条出边，可以强制添加 $n$ 条 $i\to i$ 的自环，边权 $+\infty$，编号 $+\infty$。

需要动态维护环，但正常的数据结构显然不能直接做这个工作。考虑对每个环钦定一个环上的点断掉其出边，其他的边按树的方法维护。

为了方便判断，可以钦定 LCT 上每一个连通块的根都是被断开的点。（需要注意，这会导致在代码中不能随便 makeroot）

由于每条边都有对应的一个点，可以将边权直接记在入点上。

模拟题目跳边的过程，根据一些 trivial 的分析我们只需要找到第一次断边发生的时刻，或 $s=0$ 的时刻即可。

这时需要的操作是：

• 求到根链上最小权值。
• 到根链上所有点 $val := val- z$（模拟在环上跳很多圈的过程）。
• 二分出到根链上最深的 $val=1$ 的点（需要断边的点）。

access 一下，就是 splay 的经典操作了，这里不再赘述。重点关注断边（换边）的过程：

• 断掉的是树边：
  • 直接对父亲 access 后清空父亲即可。
  • 若新边连向另一个连通块，则新边仍是树边，直接连接。
  • 否则新边是环边，这个点直接成为根（不需要任何操作）。
• 断掉的是环边：
  • 若该点是根，直接修改新边，和上面的情况类似。
  • 否则需要先断掉该边，再插入根的边，然后也和上面的情况类似了，分有没有连向新连通块讨论即可。

判断 $x$ 是否在环上的方法：检查 $x$ 与 $next(root)$ 的 LCA 是否是 $x$ 即可。

其余就是 LCT 的基础操作了。思路理清楚代码还是很好写的。

复杂度 $O((n+m)\log n)$。

#define N 200010
int n, m;
int u_[N], v_[N], w_[N];
int h[N], e[N << 1], v[N << 1], ne[N << 1], idx = -1;
void add_edge(int x, int y, int z) { ne[++idx] = h[x], h[x] = idx, e[idx] = y, v[idx] = z; }
struct Tree
{
	int mn, val, mnlazy;
	int ch[2], fa, sz;
	void pushmn(int z) { mn -= z, val -= z; mnlazy += z; }
}tr[N];
#define lson(k) tr[k].ch[0]
#define rson(k) tr[k].ch[1]
#define son(k, i) tr[k].ch[i]
#define fa(k) tr[k].fa
void pushup(int k) { tr[k].mn = std::min({tr[lson(k)].mn, tr[rson(k)].mn, tr[k].val}); tr[k].sz = tr[lson(k)].sz + tr[rson(k)].sz + 1; }
void pushdown(int k) { if(tr[k].mnlazy) { if(lson(k)) tr[lson(k)].pushmn(tr[k].mnlazy); if(rson(k)) tr[rson(k)].pushmn(tr[k].mnlazy); tr[k].mnlazy = 0; } }
int getid(int k) { return rson(fa(k)) == k; }
int notroot(int k) { return lson(fa(k)) == k || rson(fa(k)) == k; }
void rotate(int k)
{
	int f = fa(k), gf = fa(f), id = getid(k), fid = getid(f), bro = son(k, id ^ 1);
	if(notroot(f)) son(gf, fid) = k;
	son(f, id) = bro; fa(bro) = f;
	son(k, id ^ 1) = f; fa(f) = k;
	fa(k) = gf; pushup(f); pushup(k);
}
void splay(int k)
{
static int sta[N], top;
	for(int p = sta[top = 1] = k; notroot(p); sta[++top] = p = fa(p));
	for(; top; pushdown(sta[top--]));
	for(; notroot(k); rotate(k)) if(notroot(fa(k))) rotate(getid(k) == getid(fa(k)) ? fa(k) : k);
}
int access(int k) { int nx = 0; for(; k; k = fa(nx = k)) { splay(k); rson(k) = nx; pushup(k); } return nx; }
int findroot(int k)
{
	access(k); splay(k);
	while(lson(k)) k = lson(k), pushdown(k);
	splay(k); return k;
}

bool vis[N];
std::vector <int> vec[N];
void dfs0(int k, int fa)
{
	fa(k) = fa; vis[k] = 1;
	for(int nx : vec[k]) if(!vis[nx]) dfs0(nx, k);
}
void changeedge(int x, int rt)
{
	access(e[h[rt]]); int p = access(x); splay(x);
	if(x != rt) 
	{  
		access(e[h[x]]); splay(x);
		fa(x) = 0; 
	}
	h[x] = ne[h[x]];
	if(x == p && x != rt)
		splay(rt), fa(rt) = e[h[rt]];
	int q = findroot(e[h[x]]);
	if(q != x) 
	{
		splay(x);
		fa(x) = e[h[x]];
	}
	splay(x); tr[x].val = v[h[x]]; pushup(x);
}
pii dividemn(int x)
{
	if(tr[x].mn > 1) return mkp(0, 0);
	int sz = 0;
	while(1)
	{
		pushdown(x);
		if(rson(x) && tr[rson(x)].mn == 1) sz += tr[lson(x)].sz + 1, x = rson(x);
		else if(tr[x].val == 1) return mkp(x, sz + 1 + tr[lson(x)].sz);
		else x = lson(x);
	}
	debug("???\n");
	return mkp(0, 0);
}
void upd(int x, int d)
{
	if(!x || d <= 0) return;
	if(d >= tr[x].sz) { tr[x].pushmn(1); return; }
	pushdown(x);
	upd(rson(x), d); d -= tr[rson(x)].sz;
	if(d > 0) d--, tr[x].val--;
	upd(lson(x), d);
	pushup(x);
}
int jump(int x, int d)
{
	while(1)
	{
		pushdown(x);
		if(d <= tr[rson(x)].sz) { x = rson(x); continue; }
		d -= tr[rson(x)].sz;
		if(d == 1) return x;
		d--;
		x = lson(x);
	}
}
int calc(int x, int d)
{
	if(!d) return x;
	int rt = findroot(x);
	access(x); splay(x);
	if(x == e[h[rt]])
	{
		int t = std::min(d / tr[x].sz, tr[x].mn - 1);
		tr[x].pushmn(t); d -= t * tr[x].sz;
	}
	if(!d) return x;
	pii t = dividemn(x);
	if(t.fi)
	{
		upd(x, std::min(d, tr[x].sz - t.se));
		if(tr[x].sz - t.se < d) { d -= tr[x].sz - t.se; int nxt = e[h[t.fi]]; changeedge(t.fi, rt); return calc(nxt, d - 1); }
		else return e[h[jump(x, d)]];
	}
	upd(x, std::min(d, tr[x].sz)); 
	if(tr[x].sz < d) { d -= tr[x].sz; return calc(e[h[rt]], d); }
	else return e[h[jump(x, d)]];
}

void solve()
{
	tr[0].mn = inf;
	memset(h, idx = -1, sizeof(h));
	n = read(), m = read();
	for(int i = 1; i <= m; i++) u_[i] = read(), v_[i] = read(), w_[i] = read();
	for(int i = 1; i <= n; i++) add_edge(i, i, inf);
	for(int i = m; i >= 1; i--) add_edge(u_[i], v_[i], w_[i]);
	
	for(int i = 1; i <= n; i++) vec[e[h[i]]].push_back(i);
	for(int i = 1; i <= n; i++) if(!vis[i])
	{
		int p = i; for(; !vis[p]; vis[p] = 1, p = e[h[p]]);
		for(int k = i; vis[k]; vis[k] = 0, k = e[h[k]]);
		dfs0(p, 0);
	}
	for(int i = 1; i <= n; i++) tr[i].val = tr[i].mn = v[h[i]], tr[i].sz = 1;

	m = read();
	for(int i = 1; i <= m; i++)
	{
		int x = read(), d = read();
		print(calc(x, d), '\n');
	}
}