Cod sursa(job #1141676)

Utilizator toranagahVlad Badelita toranagah Data 13 martie 2014 01:13:42
Problema Iepuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#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]);
}