初学OI,圆方树入门求救
查看原帖
初学OI,圆方树入门求救
139012
wrpwrp楼主2021/7/1 10:26

这是挂了的代码

#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; 
}

但是两者的区别只在于我建了一棵圆方树还是广义圆方树, 我的dpdp是对于当前点是否是圆点来讨论的, 所以完全不懂发生啥事了。
萌新求助, 谢谢大佬/kel

2021/7/1 10:26
加载中...