30WA求调
查看原帖
30WA求调
792535
_shining楼主2024/10/21 07:42
#include <iostream>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;//命名空间
const int N = 3e5 + 5;
int d[N], vis[N]; 
vector<int> g[N], h;
int n, m, maxn = -1e9, res, s, t;
inline void dfs1(int u, int fa, int len)
{
	d[u] = len;
	for(int i = 0; i < g[u].size(); i++){
		int v = g[u][i];
		if(v == fa) continue;
		dfs1(v, u, len + 1);
	}
}
inline void dfs2(int u, int fa, int len)
{
	if(u == s){
//		for(int i = 1; i <= n; i++){
//			if(vis[i] == 1) cout << i << " ";
//		}
		for(int i = 1; i <= n; i++){
			if(vis[i] == 1) res += max(0, (int)g[i].size() - 2) + 1;
		}	
		return;
	} 
	for(int i = 0; i < g[u].size(); i++){
		int v = g[u][i];
		if(v == fa) continue;		
		vis[u] = 1;
		dfs2(v, u, len + 1);
	    vis[u] = 0;
	}
}
int main()//主函数
{
	freopen("hack.in", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1, 0, 0);
	for(int i = 1; i <= n; i++){
		if(d[i] > maxn){
			maxn = d[i];
			s = i;
		}
	}
	memset(d, 0, sizeof(d));
	maxn = -1e9;
	dfs1(s, 0, 0);
	for(int i = 1; i <= n; i++){
		if(d[i] > maxn){
			maxn = d[i];
			t = i;
		}
	}
	res = 1;
	dfs2(t, 0, 0);
	cout << res;
	return 0;//华丽结束
}
2024/10/21 07:42
加载中...