Tony102's Blog - 仙人掌
type: channel
link: https://tony102.com/index.php/tag/%E4%BB%99%E4%BA%BA%E6%8E%8C/
items: BZOJ1023 [SHOI2008]cactus仙人掌图

BZOJ1023 [SHOI2008]cactus仙人掌图
type: item
date: 2021-07-20T19:31:00+08:00
description: LinkDescription马老师要你求一棵仙人掌的直径，边权为 $1$。Sol在普通的树上直接 DP 即可. 现在考虑建出圆方树后, 在环上的特别处理对于方点，相当于我们要求必须经过环的一颗基环树的直径。也就是求$max\{f_i + f_j + dis(i,j)\}$，这个可以将环倍长用一个单调队列做。具体地, 用单调队列维护最大值，若当前位置 $i$ 和队首 $j$ 距离超过 $\frac{len}{2}$ 时,就弹出队首.Code我感觉代码其实还算好写#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[…