Submission #73723988

---

Source Code Expand

#include <bits/stdc++.h>
#define vc std::vector

vc<vc<int>> adj; 
vc<vc<int>> adj2; 
vc<int> fck;
vc<int> f;
vc<bool> vis;
int ans;

void dfs(int v, int par) {
	vis[v] = true;
	f[v] = 1;
	int max1 = 0, max2 = 0;
	for (int u : adj2[v]) {
		if (u == par) continue;
		if (!vis[u]) dfs(u, v);
		int len = (fck[u] >= 4) ? f[u] : 1;
		f[v] = std::max(f[v], 1 + len);
		if (fck[v] >= 4) {
			if (len > max1) {
				max2 = max1;
				max1 = len;
			} else if (len > max2) {
				max2 = len;
			}
		}
	}
	ans = std::max(ans, f[v]);
	if (fck[v] >= 4) {
		ans = std::max(ans, 1 + max1 + max2);
	}
}

void solve() {
	int N; std::cin >> N;
	adj.assign(N + 1, vc<int>());
	fck.assign(N + 1, 0);
	for (int i = 0; i < N - 1; i++) {
		int a, b; std::cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		fck[a]++;
		fck[b]++;
	}

	bool acfk = true;
	for (int i = 1; i <= N; i++) {
		if (fck[i] >= 3) {
			acfk = false;
			break;
		}
	}
	if (acfk) {
		std::cout << 1 << '\n';
		return;
	}

	adj2.assign(N + 1, vc<int>());
	for (int v = 1; v <= N; v++) {
		for (int u : adj[v]) {
			if (v < u && fck[v] >= 3 && fck[u] >= 3) {
				adj2[v].push_back(u);
				adj2[u].push_back(v);
			}
		}
	}

	f.assign(N + 1, 0);
	vis.assign(N + 1, false);
	ans = 1;
	for (int v = 1; v <= N; v++) {
		if (fck[v] >= 3 && !vis[v]) {
			dfs(v, -1);
		}
	}
	std::cout << ans << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int Q; std::cin >> Q;
	while (Q--) solve();
	return 0;
}

Submission Info

Judge Result