#include #include using namespace std; #define rep(i, s, t) for(int i = s, i##end = t; i <= i##end; ++i) #define per(i, s, t) for(int i = t, i##end = s; i >= i##end; --i) #define repo(i, s, t) for(int i = s, i##end = t; i < i##end; ++i) const int MAXN = 5005; int n; vector g[MAXN]; int X[MAXN], Y[MAXN]; int inputDep = 0, stdDep = 0; namespace chkInput { int fa[MAXN], dep[MAXN]; int getfa(int x) { if (fa[x] == x) return x; else { return fa[x] = getfa(fa[x]); } } void solve() { rep (i, 1, n) fa[i] = i; per (i, 1, n - 1) { int x = X[i], y = Y[i]; x = getfa(x), y = getfa(y); if (x == y) { //ERROR cerr << "not a tree" << endl; exit(1); } dep[y] = max(dep[x], dep[y]) + 1; inputDep = dep[y]; fa[x] = y; } } } namespace conquer { const int INF = 1e9; int num, Ea, Eb; int sz[MAXN], mark[MAXN][MAXN]; void getroot(int x,int fa,int sum) { sz[x] = 1; for (int t : g[x]) { if (!mark[x][t] && t != fa) { getroot(t, x, sum); sz[x] += sz[t]; int mxsz = max(sz[t], sum - sz[t]); if (mxsz < num) { num = mxsz; Ea = x, Eb = t; } } } } int partation(int x,int sum) { num = INF; getroot(x, 0, sum); if(num == INF) { return 0; } mark[Ea][Eb] = mark[Eb][Ea] = true; int A = Ea, B = Eb, SA = sum - sz[Eb], SB = sz[Eb]; return 1 + max( partation(A, SA), partation(B, SB) ); } void solve() { stdDep = partation(1, n); } } int main() { cin >> n; rep (i, 1, n - 1) { int x, y; scanf("%d %d", &x, &y); X[i] = x, Y[i] = y; g[x].push_back(y); g[y].push_back(x); } chkInput::solve(); conquer::solve(); printf("Recursion depth of your solution: %d\nRecursion depth of std solution: %d", inputDep, stdDep); return 0; }