Cod sursa(job #1169883)

Utilizator SmarandaMaria Pandele Smaranda Data 12 aprilie 2014 11:58:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include <cstdio>
#include <vector>

using namespace std;

const int SIZE = 32000;

class myIfstream {
    private :
        char buffer [SIZE];
        int cursor;
        FILE *input;
        void advance () {
            cursor ++;
            if (cursor == SIZE) {
                fread (buffer, 1, SIZE, input);
                cursor = 0;
            }
        }
    public :
        myIfstream ();
        myIfstream (const char *inputName) {
            input = fopen (inputName, "r");
            fread (buffer, 1, SIZE, input);
        }
        myIfstream &operator >> (int &value) {
            value = 0;
            while (buffer [cursor] < '0' || buffer [cursor] > '9')
                advance ();
            while (buffer [cursor] >= '0' && buffer [cursor] <= '9') {
                value = value * 10 + buffer [cursor] - '0';
                advance ();
            }
            return *this;
        }
};

myIfstream fin ("darb.in");

const int N = 100001;
vector <int> graph [N];
int n, d [N], l [N];
bool used [N];

void read () {
    int i, a, b;
    fin >> n;
    for (i = 1; i < n; i ++) {
        fin >> a >> b;
        graph [a].push_back (b);
        graph [b].push_back (a);
    }
}

void dfs (int node) {
    vector <int> :: iterator it;
    int max1, max2, child;
    used [node] = 1;
    l [node] = 0;
    d [node] = 0;
    max1 = max2 = 0; // max1 > max2
    for (it = graph [node].begin (); it != graph [node].end (); it ++) {
        child = *it;
        if (!used [child]) {
            dfs (child);
            l [node] = max (l [node], l [child] + 1);
            if (l [child] > max1) {
                max2 = max1;
                max1 = l [child];
            }
            else
                if (l [child] > max2)
                    max2 = l [child];
            d [node] = max (d [node], d [child]);
        }
    }
    d [node] = max (d [node], max1 + max2 + 1);
    if (l [node] == 0) {// frunza
        l [node] = 1;
        d [node] = 1;
    }
}

void solve () {
    dfs (1);
    printf ("%d\n", d [1]);
}

int main () {
    freopen ("darb.out", "w", stdout);

    read ();
    solve ();
    return 0;
}