Pagini recente » Cod sursa (job #1190023) | Cod sursa (job #2302765) | Cod sursa (job #3154237) | Cod sursa (job #2823199) | Cod sursa (job #1141676)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("trib.in");
ofstream fout("trib.out");
const int INF = 1 << 30;
const int MAX_N = 100100;
int N;
vector<int> graph[MAX_N];
vector<pair<int, int>> vals[MAX_N];
int last_free[MAX_N];
bool visited[MAX_N];
int best[MAX_N];
int result;
void readfin();
void dfs1(int node);
void dfs2(int node, int up=0);
inline void update_node(int node);
int main() {
readfin();
dfs1(1);
fill(visited, visited + N + 1, 0);
dfs2(1);
fout << result;
return 0;
}
void readfin() {
fin >> N;
for (int i = 1, a, b; i < N; i += 1) {
fin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
}
void dfs1(int node) {
visited[node] = true;
for (auto next: graph[node]) {
if (visited[next]) continue;
dfs1(next);
vals[node].push_back(make_pair(best[next], 1));
}
sort(vals[node].begin(), vals[node].end());
update_node(node);
}
void dfs2(int node, int up) {
visited[node] = true;
if (up != 0) {
vals[node].insert(
lower_bound(vals[node].begin(), vals[node].end(),
make_pair(up, 0)), make_pair(up, 0));
update_node(node);
}
for (auto next: graph[node]) {
if (visited[next]) continue;
int loc =
upper_bound(
vals[node].begin(),
vals[node].end(),
make_pair(best[next], INF)) -
vals[node].begin();
int nbc = best[node];
if (loc < 2 or
vals[node][loc - 1].second !=
vals[node][loc - 2].second) {
if (last_free[node] <= loc) {
nbc -= 1;
}
}
dfs2(next, nbc);
}
}
inline void update_node(int node) {
best[node] = 1;
last_free[node] = 0;
for (size_t i = 0; i < vals[node].size(); i += 1) {
if (vals[node][i].first >= best[node]) {
best[node] += 1;
} else {
last_free[node] = i;
}
vals[node][i].second = best[node];
}
result = max(result, best[node]);
}