「题解」[NOI2014] 魔法森林

link
\(ans=maxa + maxb\)。瓶颈在如何寻找路径。
若只有一个因素？跑 mst即可。所以枚举 a（或排序）, 我们可以得到一个 n^2log 的做法，这个暴力建树都要 nlog...
如何减少加边次数？自然想到用上一次加边后的版本。
所有边先按照 \(a\) 排序，每次在新的树上连边（边权为 \(b\)）。若两个点之间没有路径，直接连接。否则，删去两个点路径中最大的边，在将它们连接。
很容易想到用 lct 维护，但是lct 不支持有边权，所以就把边也搞成点即可。
关于要删去最大边的证明：假设是先加上这条边再在环上删去，如果删去的最大边，任意两个点都可以以 \(\leqslant\) \(val_{max}\) 的价值到达，所以即证。

// viva la vida
#include 
#include 
#include 
#include 
#include 
#define mr make_pair
#define pr pair 
#define ls tree[x].son[0]
#define rs tree[x].son[1]
#define fs tree[x].fa
#define LL long long
using namespace std;
const int MAXN = 2e5 + 5, inf = 0x3f3f3f3f;
int T, Tag, n, q, ans1, ansnum;
LL a[MAXN], b[MAXN];
struct Edge {
	int X, Y, A, B;
	bool operator < (const Edge P) const { return A < P.A; }
}edge[MAXN];
struct LCT {
	struct Node {
		int son[2], fa, siz, rev, val, mx, num;
	}tree[MAXN];
	void newnode(int x, int v) { tree[x].siz = 1; tree[x].val = v; tree[x].mx = v; tree[x].num = x; }
	bool isroot(int x) { return tree[fs].son[0] != x && tree[fs].son[1] != x; }
	void update(int x) {
		if(x == 0) return;
		tree[x].siz = tree[ls].siz + tree[rs].siz + 1;
		if(tree[ls].mx > tree[rs].mx) tree[x].mx = tree[ls].mx, tree[x].num = tree[ls].num;
		else tree[x].mx = tree[rs].mx, tree[x].num = tree[rs].num;
		if(tree[x].val > tree[x].mx) tree[x].mx = tree[x].val, tree[x].num = x;
	}
	void Rev(int x) { tree[x].rev ^= 1; swap(ls, rs); }
	void spread(int x) {
		if(tree[x].rev) { Rev(ls); Rev(rs); tree[x].rev = 0; }
	}
	void devolve(int x) {
		if(!isroot(x)) devolve(fs);
		spread(x);
	}
	void rotate(int x) {
		int y = fs, grand = tree[fs].fa, f = (tree[y].son[0] == x);
		if(!isroot(y)) tree[grand].son[tree[grand].son[1] == y] = x;
		fs = grand;
		tree[y].son[!f] = tree[x].son[f]; tree[tree[x].son[f]].fa = y;
		tree[x].son[f] = y; tree[y].fa = x; update(y); update(x);
	}
	void splay(int x) {
		devolve(x);
		for(; !isroot(x); rotate(x)) if(!isroot(fs)) (tree[tree[fs].fa].son[1] == fs) == (tree[fs].son[1] == x) ? rotate(fs) : rotate(x);
	} 
	int Access(int x) {
		int las;
		for(las = 0; x; las = x, x = fs) splay(x), rs = las, update(x);
		return las;
	}
	void makeroot(int x) { x = Access(x); Rev(x); }
	void Link(int x, int y) { makeroot(x); splay(x); fs = y; }
	void Cut(int x, int y) { makeroot(x); Access(y); splay(y); tree[y].son[0] = fs = 0; update(y); }
	int Find(int x) {
		Access(x); splay(x); devolve(x); 
		while(ls) x = ls, spread(ls);
		splay(x); return x;
	}
	void ask(int x, int y) { makeroot(x); Access(y); splay(y); ans1 = tree[y].mx; ansnum = tree[y].num; }
}lct;
int main() {
	int n, m, ans = inf; scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++) lct.newnode(i, 0);
	for(int i = 1; i <= m; i ++) scanf("%d%d%d%d", &edge[i].X, &edge[i].Y, &edge[i].A, &edge[i].B);
	sort(edge + 1, edge + 1 + m);
	for(int i = 1; i <= m; i ++) {
		lct.newnode(n + i, edge[i].B);
		if(lct.Find(edge[i].X) ^ lct.Find(edge[i].Y)) lct.Link(edge[i].X, n + i), lct.Link(edge[i].Y, n + i);
		else {
			lct.ask(edge[i].X, edge[i].Y);
			if(ans1 > edge[i].B) {
				lct.Cut(edge[ansnum - n].Y, ansnum); lct.Link(edge[i].X, n + i), lct.Link(edge[i].Y, n + i);
			}
		}
		if(lct.Find(1) ^ lct.Find(n)) continue;
		lct.ask(1, n); ans = min(ans, edge[i].A + ans1);
	}
	printf("%d", ans == inf ? -1 : ans);
	return 0;
}
LCT

相关

LCT 学习笔记

[洛谷P3345][BZOJ4573][ZJOI2016]大森林（LCT）

BUUFTC-日刷-[FireshellCTF2020]ScreenShooter-PhantomJS文件读取漏洞

LCT

bzoj3510 首都 LCT 维护子树信息+树的重心

nginx.service的作业失败，因为控制进程已退出，错误代码为。 有关详细信息，请参阅“system

[bzoj] 2002 弹飞绵羊 || LCT

标签