BZOJ1023 [SHOI2008]cactus仙人掌图

tony102

2021 年 07 月 20 日

1756 次浏览

暂无评论

632字数

题解

[Link](https://hydro.ac/d/bzoj/p/1023)

## Description

马老师要你求一棵仙人掌的直径，边权为 $1$。

## Sol

在普通的树上直接 DP 即可. 现在考虑建出圆方树后, 在环上的特别处理

对于方点，相当于我们要求必须经过环的一颗基环树的直径。也就是求$max\{f_i + f_j + dis(i,j)\}$，这个可以将环倍长用一个单调队列做。具体地, 用单调队列维护最大值，若当前位置 $i$ 和队首 $j$ 距离超过 $\frac{len}{2}$ 时,就弹出队首.

## Code

我感觉代码其实还算好写

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef std::vector < int > vec;
const int SIZE = 1e5 + 5, SIZE_M = 5e6 + 5;
const int inf = 2e9;

int n, N, m, num, tim, ans;
int head[SIZE], fa[SIZE], dfn[SIZE], cir[SIZE], f[SIZE], cha[SIZE], q[SIZE];
vec g[SIZE];

struct node {
	int to, nxt;
} edge[SIZE_M << 1];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

void addEdge(int u, int v) {
	edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void dfs(int u) {
	dfn[u] = ++ tim;
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == fa[u]) continue;
		if (!dfn[v]) {
			cir[u] = 0, fa[v] = u; dfs(v);
			if (!cir[u]) g[u].emplace_back(v), g[v].emplace_back(u);
		}
		else if (dfn[v] < dfn[u]) {
			int x = u; ++ N;
			g[x].emplace_back(N), g[N].emplace_back(x);
			do {
				x = fa[x]; g[x].emplace_back(N), g[N].emplace_back(x); cir[x] = 1;
			} while (x != v);
		}
	}
}

void dp(int u, int anc) {
	for (auto v: g[u]) {
		if (v != anc) dp(v, u);
	}
	if (u <= n) {
		int mx = 0;
		for (auto v: g[u]) {
			if (v == anc) continue;
			mx = std::max(mx, f[v] + 1);
			if (mx > f[u]) std::swap(f[u], mx);
		}
		ans = std::max(f[u] + mx, ans);
	}
	else {
		int head = 1, tail = 0, cnt = 0;
		for (auto v: g[u]) {
			if (v == anc) continue;
			cha[++ cnt] = v;
		}
		for (int i = 1; i <= cnt; ++ i) cha[i + cnt] = cha[i];
		for (int i = 1; i <= cnt * 2; ++ i) {
			while (head <= tail && (i - q[head]) > (cnt + 1) / 2) ++ head;
			if (i >= cnt) ans = std::max(ans, f[cha[q[head]]] + f[cha[i]] + i - q[head]);
			while (head <= tail && f[cha[i]] - i >= f[cha[q[tail]]] - q[tail]) -- tail;
			q[++ tail] = i;
		}
		for (int i = 1; i <= cnt / 2; ++ i) f[u] = std::max(f[u], f[cha[i]] + i - 1);
		for (int i = cnt / 2 + 1; i <= cnt; ++ i) f[u] = std::max(f[u], f[cha[i]] + cnt - i);
	}
}

int main() {
	n = N = read(), m = read();
	for (int i = 1, tot, u, v; i <= m; ++ i) {
		tot = read(), u = v = 0;
		for (int j = 1; j <= tot; ++ j) {
			v = read();
			if (u) { addEdge(u, v); addEdge(v, u); }
			u = v;
		}
	}
	dfs(1); dp(1, 0);
	printf("%d\n", ans);
	return 0;
}
```

最后修改：2021 年 09 月 07 日