Pagini recente » Monitorul de evaluare | Cod sursa (job #997946) | Cod sursa (job #1386687) | Cod sursa (job #2201314) | Cod sursa (job #2779940)
//
// Created by Andrei Covaci on 03.09.2021.
//
#include <fstream>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
#define INPUT "darb.in"
#define OUTPUT "darb.out"
//#define INPUT "input.in"
//#define OUTPUT "output.out"
int n, maxg;
unordered_map<int, vector<int>> adj;
bool vis[100001];
int read() {
ifstream in(INPUT);
int a, b;
in >> n;
n--;
for(; n; --n) {
in >> a >> b;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
in.close();
return a;
}
int solve(int n) {
vis[n] = true;
if(adj[n].size() == 1) {
if (!vis[adj[n][0]])
return solve(adj[n][0]) + 1;
else
return 1;
}
if(adj[n].size() == 2 && (vis[adj[n][0]] ^ vis[adj[n][1]])) {
return ( vis[adj[n][0]] ? solve(adj[n][1]) : solve(adj[n][0]) ) + 1;
}
int max1 = 0, max2 = 0, temp;
for(int c : adj[n]) {
if(!vis[c]) {
temp = solve(c);
std::remove(adj[c].begin(), adj[c].end(), n);
if (temp > max1) {
max2 = max1;
max1 = temp;
} else if (temp > max2) {
max2 = temp;
}
}
}
maxg = max(maxg, max1 + max2 + 1);
return max1 + 1;
}
void print(int res) {
ofstream out(OUTPUT);
if(res > maxg)
out << res;
else
out << maxg;
out.close();
}
int main() {
auto in = read();
auto out = solve(in);
print(out);
return 0;
}