[training Day8] [luogu_p6335] staza [tarjan]

Ideas ：

We set up fi Indicates the current downward link , Walk back i Maximum path to
gi It means going down at the current point , Don't walk back i Maximum path to
set up w=gi-fi, that gi=fi+w
If i To j The side of is not in the ring , That obviously won't be right fi Contribute to , So let's finish everything first fi, Then go down gj, therefore w=gi+fi+1-fi, Take all the maximum

Then if i To j It's in the ring , Then go through every point in the ring first , Put their f All finished （ This is obviously the biggest ）, Contribution: u. Then set v It means that you go to a certain point in the process of walking and don't continue , Instead, it's the one who walks it g, be v=max（dis(i,j)+${\sum }_k{f}_k+g_j$）,j At which point do you stay ,k yes i Go to the j All passing points . Attention from i To j There are two directions , So we have to calculate . therefore w=max(v-u).

The final answer is g1

$code$

#include<iostream>
#include<cstdio>

using namespace std;

const int MAXN = 1e5 + 10;

int n, m;
int cnt, dfn[MAXN], low[MAXN], f[MAXN], g[MAXN], fa[MAXN];
int tot, head[MAXN];

struct node {
    
	int to, next;
}b[MAXN * 2];

void add(int x, int y) {
    
	b[++ tot] = (node) {
     y, head[x] };
	head[x] = tot;
}

void tarjan(int x) {
    
	dfn[x] = low[x] = ++ cnt;
	int w = 0;
	for(int i = head[x]; i; i = b[i].next) {
    
		int y = b[i].to;
		if(y == fa[x]) continue;
		if(!dfn[y]) {
    
			fa[y] = x;
			tarjan(y);
			low[x] = min(low[y], low[x]);
			if(low[y] > dfn[x]) w = max(w, g[y] + 1);
		}
		else low[x] = min(low[x], dfn[y]);
	}
	for(int i = head[x]; i; i = b[i].next) {
    
		int y = b[i].to;
		if(dfn[y] > dfn[x] && fa[y] != x) {
    
			int u = 1, v = 0;
			for(int k = y; k != x; k = fa[k])
				v = max(v, u + g[k]), u += f[k] + 1; 
			f[x] += u;
			int tmp = u;
			for(int k = y; k != x; k = fa[k])
				tmp -= f[k] + 1, v = max(v, tmp + g[k]);
			w = max(w, v - u);
		}
	}
	g[x] = w + f[x];
}

int main() {
    
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++) {
    
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y), add(y, x);
	}
	tarjan(1);
	printf("%d", g[1]);
	return 0;
}