21 Days Training // Day 14

T0. diameter

My idea : greedy

For every query, record the depth of 3 subtrees of the root, and find the sum of the maximum 2.

Code :

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

int main() {
    int Q;cin >> Q;
    vector<int> Par, Depth;
    for (int i=0;i<4;i++) {
        if (i==0) {
            Par.push_back(-1);
            Depth.push_back(0);
        }
        else {
            Par.push_back(i);
            Depth.push_back(1);
        }
    }
    int mdL=1, mdM=1, mdR=1;
    for (int i=0;i<Q;i++) {
        int T;cin >> T;T--;
        Depth.push_back(Depth[T]+1);
        Depth.push_back(Depth[T]+1);
        Par.push_back(Par[T]);
        Par.push_back(Par[T]);
        if (Par[T]==1) mdL=max(mdL, Depth[T]+1);
        if (Par[T]==2) mdM=max(mdM, Depth[T]+1);
        if (Par[T]==3) mdR=max(mdR, Depth[T]+1);
        cout << mdL+mdM+mdR-min(mdL, min(mdM, mdR)) << endl;
    }

    return 0;
}

Bugs :

It is completely wrong, suppose that the style of tree is :

If we use the algorithm above, the result is 5.
However, the true diameter of the tree is 6. (Left subtree of root).

(However, it still can get 40)