【Luogu P5994】 [PA2014]Kuglarz

题目大意：

给定 (N) 个点，每个点可能有一个标记，可以通过 (c_{i,j}) 知道区间 ([i,j]) 的奇偶性，问你至少需要花费多少，才能保证猜出哪些点有标记。

正文：

求导过程：

我做题时开始想的是通过知道两个区间 ([l,r-1],[l,r]) 的奇偶性直接得到 (r) 是否标记。而我们可以知道 ([0,r],[l,r]) 得到 ([0,l-1]) 的奇偶性，将区间作为树的节点，每次给出 ([l,r]) 的代价 (w) 时，连两点 ([0,r],[0,l-1]) 为一代价是 (w) 的线，即可最小生成树。

代码：

int main()
{
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = i; j <= n; j++)
		{
			int w;
			scanf ("%d", &w);
			add(i - 1, j, w);
		}
	}
	sort(e + 1, e + 1 + tot, cmp);
	for (int i = 1; i <= tot ; i++)
	{
		int f = FIND(e[i].from), t = FIND(e[i].to); 
		if (f == t) continue;
		fa[f] = t;
		ans += e[i].w * 1ll;
	}
	printf ("%lld", ans);
	return 0;
}