求n个点的边不带权的仙人掌的直径. 仙人掌上两点间距离定义为两点间最短路. (1≤n≤50000) 人生第一道静态仙人掌, 虽然写得不美......WC的时候就想写, 但是没有头绪.
先自己yy了一发. 每个点的最远点似乎求起来不是很容易......试一下树上每棵子树最深+次深那种策略. 然后学习松爷的论文, 发现环上的情形想得太简单了. QAQ 直径是最长的最短路, 所以确实需要一个单调队列.
深度优先遍历一棵仙人掌 首先, 这是无向图, 所以每条边以两种方向各添加了一次. 需要判断(u,v)是一条真的边, 而非(fa[u],u)的反向边. 可以简单地在v == fa[u]时将(u,v)忽略, 虽然这样把两个点的环也当成了桥, 但是通常没有影响.
dfs的时候可以开一个栈记录所有结点, 也可以设置fa, 用来遍历一个环.
dfn记录每个点的首次访问时间. 设当前点为u, 有一条边(u,v).
如果v还没有访问, 那就访问它.
如果v已经访问过了, 且dfn[v] < dfn[u], 说明找到一个以v为父亲的环; 如果dfn[v] > dfn[u], 说明v在以u为父亲的环中, 且已经处理过, 忽略即可.
当v已经访问过时, 也有另一种策略. 如果dfn[v] < dfn[u], 忽略之; 如果dfn[v] > dfn[u], 再来处理这个环. 好处在于, 环上的信息此时已经计算完毕.
求仙人掌的直径 用BFS给仙人掌划分层次, 考虑一条路径的最高点. 最高点的附近有两种情况: 和最高点所在环有边相交, 最高点不在环中或着和该环没有边相交. 一个点可以在很多环中.
第二种情况, 用不同分支的最深+次深更新答案. 第一种情况, 需要用 环上结点对 向环外延伸的最大长度之和 + 两点间距离(最短路) 来更新答案. 用单调队列扫一圈即可.
实现 我是严格遵循以上叙述实现的......先DFS一遍求出仙人掌的结构, 再DFS一遍做DP.
ydc神犇的题解 非常简洁. 不用把仙人掌的每个环刨出来, 求结构的同时就可以DP. 遇到桥边, 更新F值 (为了判断桥边, 记录low). 处理完桥边之后再处理环. 用不着显式地记录最深和次深.
const int N = 5e4;
struct Edge {
int v, nxt;
} E[4*N];
int adj[N+1];
inline void add(int u, int v)
{
static int ptr = 2;
E[ptr] = (Edge){v, adj[u]};
adj[u] = ptr++;
}
vector<int> son[N+1], sz[N+1];
int dfs_clock, cir[N+1], dfn[N+1], S[N+1], top;
pair<int, int> d[N+1][2];
bool used[2*N];
void build(int u)
{
dfn[u] = ++dfs_clock;
S[top++] = u;
for (int i = adj[u]; i; i = E[i].nxt) {
if (used[i>>1]) continue;
used[i>>1] = true;
int v = E[i].v;
if (dfn[v]) {
if (dfn[v] < dfn[u]) {
int cnt = 0;
for (int j = top-1; S[j] != v; --j) {
++cnt;
cir[S[j]] = v;
son[v].push_back(S[j]);
}
sz[v].push_back(cnt);
}
} else {
build(v);
if (!cir[v]) {
son[u].push_back(v);
sz[u].push_back(1);
}
}
}
--top;
}
int dfs(int u)
{
int st = 0;
rep (i, 0, sz[u].size()) {
int x = 0;
rep (j, st, st + sz[u][i]) {
int t = min(j-st+1, sz[u][i]-j+st) + dfs(son[u][j]);
x = max(x, t);
}
st += sz[u][i];
if (x >= d[u][0].first) {
d[u][1] = d[u][0];
d[u][0] = make_pair(x, i);
} else if (x > d[u][1].first)
d[u][1] = make_pair(x, i);
}
return d[u][0].first;
}
int circle(int s[], int d[], int n)
{
static int Q[2*N];
int front = 0, rear = 0, j = 1, m = n/2, ans = 0;
Q[rear++] = 0;
rep (i, 0, n) {
if (Q[front] == i) ++front;
while (j-i <= m) {
while (rear > front && Q[rear-1] + d[Q[rear-1]] <= j + d[j]) --rear;
Q[rear++] = j++;
}
ans = max(ans, Q[front] - i + d[Q[front]] + d[i]);
}
return ans;
}
int main()
{
int n, m, ans = 0;
scanf("%d%d", &n, &m);
rep (i, 0, m) {
int k, x, y;
scanf("%d%d", &k, &x);
while (--k) {
scanf("%d", &y);
add(x, y);
add(y, x);
x = y;
}
}
build(1);
dfs(1);
rep (i, 1, n+1) {
ans = max(ans, d[i][0].first + d[i][1].first);
int st = 0;
rep (j, 0, sz[i].size()) {
static int s[2*N], d[2*N];
int top = 1;
s[0] = i;
d[0] = ::d[i][0].second == j ? ::d[i][1].first : ::d[i][0].first;
rep (k, st, st + sz[i][j]) {
s[top] = son[i][k];
d[top++] = ::d[son[i][k]][0].first;
}
st += sz[i][j];
copy(s, s+top, s+top);
copy(d, d+top, d+top);
ans = max(ans, circle(s, d, top));
}
}
printf("%d\n", ans);
return 0;
}