spoj: classical ⇝ rtree ⇝ Roger and tree

rtree.cc

#include <bits/stdc++.h>
using namespace std;
#define builtin_gcd __gcd


static struct IO {
    char tmp[1 << 10];
    // fast input routines
    char cur;

    // #define nextChar() (cur = getc_unlocked(stdin))
    // #define peekChar() (cur)
    inline char nextChar() {
        return cur = getc_unlocked(stdin);
    }
    inline char peekChar() {
        return cur;
    }

    inline operator bool() {
        return peekChar();
    }
    inline static bool isBlank(char c) {
        return (c < '-' && c);
    }
    inline bool skipBlanks() {
        while (isBlank(nextChar()));
        return peekChar() != 0;
    }

    inline IO& operator >> (char & c) {
        c = nextChar();
        return *this;
    }

    inline IO& operator >> (char * buf) {
        if (skipBlanks()) {
            if (peekChar()) {
                *(buf++) = peekChar();
                while (!isBlank(nextChar()))
                    *(buf++) = peekChar();
            }
            *(buf++) = 0;
        }
        return *this;
    }

    inline IO& operator >> (string & s) {
        if (skipBlanks()) {
            s.clear();
            s += peekChar();
            while (!isBlank(nextChar()))
                s += peekChar();
        }
        return *this;
    }

    inline IO& operator >> (double & d) {
        if ((*this) >> tmp)
            sscanf(tmp, "%lf", &d);
        return *this;
    }

    #define defineInFor(intType) \
        inline IO& operator >>(intType & n) { \
            if (skipBlanks()) { \
                int sign = +1; \
                if (peekChar() == '-') { \
                    sign = -1; \
                    n = nextChar() - '0'; \
                } else \
                    n = peekChar() - '0'; \
                while (!isBlank(nextChar())) { \
                    n += n + (n << 3) + peekChar() - 48; \
                } \
                n *= sign; \
            } \
            return *this; \
        }

    defineInFor(int)
    defineInFor(unsigned int)
    defineInFor(long long)

        // fast output routines

        //#define putChar(c) putc_unlocked((c), stdout)
        inline void putChar(char c) {
            putc_unlocked(c, stdout);
        }
        inline IO& operator << (char c) {
            putChar(c);
            return *this;
        }
        inline IO& operator << (const char * s) {
            while (*s) putChar(*s++);
            return *this;
        }

        inline IO& operator << (const string & s) {
            for (int i = 0; i < (int)s.size(); ++i)
                putChar(s[i]);
            return *this;
        }

        char * toString(double d) {
            sprintf(tmp, "%lf%c", d, '\0');
            return tmp;
        }
        inline IO& operator << (double d) {
            return (*this) << toString(d);
        }


    #define defineOutFor(intType) \
        inline char * toString(intType n) { \
            char * p = (tmp + 30); \
            if (n) { \
                bool isNeg = 0; \
                if (n < 0) isNeg = 1, n = -n; \
                while (n) \
                    *--p = (n % 10) + '0', n /= 10; \
                if (isNeg) *--p = '-'; \
            } else *--p = '0'; \
            return p; \
        } \
        inline IO& operator << (intType n) { return (*this) << toString(n); }

    defineOutFor(int)
    defineOutFor(long long)

    #define endl ('\n')
    #define cout __io__
    #define cin __io__
} __io__;

void setParent(map<int, pair<vector<int>, int > >& tree, int root) {
    tree[root].second = -1;
    stack<int> st;
    st.push(root);
    while(st.size()) {
        int node = st.top(); st.pop();
        for (int child: tree[node].first) {
            if (child != tree[node].second) {
                tree[child].second = node;
                st.push(child);
            }
        }
    }
}

void longestPath(int root, map<int, pair<vector<int>, int > >& tree, vector<int>& lp) {
    // traversing
    stack<int> trav;
    stack<int> resolve;
    trav.push(root);
    while(trav.size()) {
        int node = trav.top(); trav.pop();
        resolve.push(node);
        for(int c: tree[node].first) {
            if (c != tree[node].second) {
                trav.push(c);
            }
        }
    }
    vector<int> depths(lp.size());
    while(resolve.size()) {
        int node = resolve.top(); resolve.pop();
        int d1 = 0, d2 = 0, clp = 0;
        for(int c: tree[node].first) {
            if (c != tree[node].second) {
                if (lp[c] > clp)
                    clp = lp[c];
                if (depths[c] >= d1) {
                    d2 = d1;
                    d1 = depths[c];
                }
                else if(depths[c] > d2) {
                    d2 = depths[c];
                }
            }
        }
        depths[node] = d1 + 1;
        lp[node] = max(clp, d1 + d2 + 1);
    }
}

int main() {
    map<int, pair<vector<int>, int > > tree;
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u - 1].first.push_back(v - 1);
        tree[v - 1].first.push_back(u - 1);
    }
    vector<int> lp(n);

    int r, q;
    cin >> r >> q;
    setParent(tree, r - 1);

    longestPath(r - 1, tree, lp);
    // for (int c:lp){
    //     cout << c << ' ';
    // }
    // cout << endl;
    for (int i = 0; i < q; ++i) {
        int query;
        cin >> query;
        cout << lp[query - 1] - 1 << endl;
    }
    return 0;
}