这是挂了的代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
const int M = 4e5 + 10;
const int INF = 0x3f3f3f3f;
struct edge {
int to, next;
} e[M];
int cnt, head[N];
void push(int x, int y) {
e[++ cnt] = (edge) {y, head[x]}; head[x] = cnt;
}
int n, m, tot;
vector<int> vec[N];
int dfn[N], low[N], stk[N], top;
int cc;
void tarjan(int x, int fx) {
stk[++ top] = x;
dfn[x] = low[x] = ++ dfn[0];// cerr << x <<endl;
for(int i = head[x]; i; i = e[i].next) {
int y = e[i].to;
if(y == fx) continue;
if(! dfn[y]) {
tarjan(y, x);
low[x] = min(low[x], low[y]);
if(low[y] == dfn[x]) {
tot ++;
vec[tot].push_back(x); //cerr << tot << ' ' << x <<endl;
vec[x].push_back(tot); cc ++;
while(1) {
vec[tot].push_back(stk[top]); //cerr << tot << ' ' << stk[top] << endl;
vec[stk[top]].push_back(tot); cc++;
top --;
if(stk[top + 1] == y) break;
}
}
else if(low[y] > dfn[x]) -- top, vec[x].push_back(y), vec[y].push_back(x), cc ++;
} else low[x] = min(low[x], dfn[y]);
//if(low[y] > dfn[x]) vec[x].push_back(y), vec[y].push_back(x), cc ++;
}
}
struct Node {
int a, b;
Node() { a = 0; b = -INF; }
void update(int v) {
if(v > a) swap(a, v);
if(v > b) swap(b, v);
}
} dp[N];
int Ans;
void dfs(int x, int fx) {
if(x <= n) {
for(int y : vec[x]) {
if(y == fx) continue;
dfs(y, x);
if(y > n) continue;
dp[x].update(dp[y].a + 1);
Ans = max(Ans, dp[x].a);
Ans = max(dp[x].a + dp[x].b, Ans);
}
}
else {
static int g[N << 1], q[N << 1];
int num = 0;
for(int y : vec[x])
if(y != fx) dfs(y, x);
for(int y : vec[x])
g[++ num] = dp[y].a;
//cerr <<"Case" <<endl;
//for(int i = 1; i <= num; i ++) cerr <<g[i] << ' '; cerr <<endl;
for(int i = 2; i <= num; i ++) dp[fx].update(g[i] + min(i - 1, num - i + 1));
for(int i = 1; i <= num; i ++) g[i + num] = g[i];
int l = 1, r = 0;
q[++ r] = 1;
for(int i = 2; i <= (num << 1); i ++) {
while(l <= r && i - q[l] > num / 2) l ++;
int j = q[l];
Ans = max(Ans, i - j + g[j] + g[i]);
while(l <= r && g[q[r]] - q[r] <
g[i] - i) r --;
q[++ r] = i;
}
}
}
int main() {
ios :: sync_with_stdio(false);
cin >> n >> m; tot = n;
for(int i = 1; i <= m; i ++) {
int nd, x;
cin >> nd >> x; nd --;
while(nd --) {
int y;
cin >> y;
push(x, y);
push(y, x);
//cerr << x << ' ' << y << endl;
x = y;
}
}
tarjan(1, 0);
//cerr << tot << ' ' << cc << endl;
dfs(1, 0);
cout << Ans << endl;
return 0;
}
这是没挂的
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
const int M = 4e5 + 10;
const int INF = 0x3f3f3f3f;
struct edge {
int to, next;
} e[M];
int cnt, head[N];
void push(int x, int y) {
e[++ cnt] = (edge) {y, head[x]}; head[x] = cnt;
}
int n, m, tot;
vector<int> vec[N];
int dfn[N], low[N], stk[N], top;
int cc;
void tarjan(int x, int fx) {
stk[++ top] = x;
dfn[x] = low[x] = ++ dfn[0];// cerr << x <<endl;
for(int i = head[x]; i; i = e[i].next) {
int y = e[i].to;
// if(y == fx) continue;
if(! dfn[y]) {
tarjan(y, x);
low[x] = min(low[x], low[y]);
if(low[y] == dfn[x]) {
tot ++;
vec[tot].push_back(x); //cerr << tot << ' ' << x <<endl;
vec[x].push_back(tot); cc ++;
while(1) {
vec[tot].push_back(stk[top]); //cerr << tot << ' ' << stk[top] << endl;
vec[stk[top]].push_back(tot); cc++;
top --;
if(stk[top + 1] == y) break;
}
}
// else if(low[y] > dfn[x]) -- top, vec[x].push_back(y), vec[y].push_back(x), cc ++;
} else low[x] = min(low[x], dfn[y]);
//if(low[y] > dfn[x]) vec[x].push_back(y), vec[y].push_back(x), cc ++;
}
}
struct Node {
int a, b;
Node() { a = 0; b = -INF; }
void update(int v) {
if(v > a) swap(a, v);
if(v > b) swap(b, v);
}
} dp[N];
int Ans;
void dfs(int x, int fx) {
if(x <= n) {
for(int y : vec[x]) {
if(y == fx) continue;
dfs(y, x);
if(y > n) continue;
dp[x].update(dp[y].a + 1);
Ans = max(Ans, dp[x].a);
Ans = max(dp[x].a + dp[x].b, Ans);
}
}
else {
static int g[N << 1], q[N << 1];
int num = 0;
for(int y : vec[x])
if(y != fx) dfs(y, x);
for(int y : vec[x])
g[++ num] = dp[y].a;
//cerr <<"Case" <<endl;
//for(int i = 1; i <= num; i ++) cerr <<g[i] << ' '; cerr <<endl;
for(int i = 2; i <= num; i ++) dp[fx].update(g[i] + min(i - 1, num - i + 1));
for(int i = 1; i <= num; i ++) g[i + num] = g[i];
int l = 1, r = 0;
q[++ r] = 1;
for(int i = 2; i <= (num << 1); i ++) {
while(l <= r && i - q[l] > num / 2) l ++;
int j = q[l];
Ans = max(Ans, i - j + g[j] + g[i]);
while(l <= r && g[q[r]] - q[r] <
g[i] - i) r --;
q[++ r] = i;
}
}
}
int main() {
ios :: sync_with_stdio(false);
cin >> n >> m; tot = n;
for(int i = 1; i <= m; i ++) {
int nd, x;
cin >> nd >> x; nd --;
while(nd --) {
int y;
cin >> y;
push(x, y);
push(y, x);
//cerr << x << ' ' << y << endl;
x = y;
}
}
tarjan(1, 0);
cerr << tot << ' ' << cc << endl;
dfs(1, 0);
cout << Ans << endl;
return 0;
}
但是两者的区别只在于我建了一棵圆方树还是广义圆方树, 我的dp是对于当前点是否是圆点来讨论的, 所以完全不懂发生啥事了。
萌新求助, 谢谢大佬/kel