Informatics #889 stress

//#pragma optimization_level 3
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <string>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <string.h>
#include <stack>
#include <assert.h>
#include <list>
#include <time.h>
#include <memory>
#include <chrono>
using namespace std;
//
//#define LOGGING
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
//#define cin in
//#define cout out
#define ll long long
#define db double
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define ms multiset
#define pb push_back
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define PI acos(-1.0)
//#define sort(a, b) sort(a.begin(), a.end(), b())
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
ifstream in("input.txt");
ofstream out("output.txt");

const int MAX_N = 1e5;

struct pth {
    int u1, u2, last;
};

int maxd[MAX_N], sub_path[MAX_N], path1[MAX_N];
int _maxd[MAX_N];
pii _sub_path[MAX_N];
pth _path1[MAX_N];

vector<int> g[MAX_N], ch[MAX_N];
int n;

int ans = 0;
pii path[2];

bool vis[MAX_N];
void find_maxi_cycle(int st, int v, int len, int &max_len) {
    vis[v] = 1;

    for (int to : g[v]) {
        if (to == st)
            max_len = max(max_len, len);

        if (!vis[to])
            find_maxi_cycle(st, to, len + 1, max_len);
    }

    vis[v] = 0;
}

int find_maxi_cycle() {
    int max_len = 0;
    for (int v = 0; v < n; v++)
        find_maxi_cycle(v, v, 1, max_len);
    return max_len;
}

template<typename T>
void upd(int& val, int upd, T& pr, const T& cur_pr) {
    if (upd > val) {
        val = upd;
        pr = cur_pr;
    }
}

void upd_ans(int upd, pii a, pii b) {
    if (upd > ans) {
        ans = upd;
        path[0] = a;
        path[1] = b;
    }
}

void upd_ans(int upd, pii a) {
    if (upd > ans) {
        ans = upd;
        path[0] = a;
        path[1] = { -1, -1 };
    }
}

void calc(int v) {
    upd(maxd[v], 1, _maxd[v], v);

    //calculates dp values
    for (int to : ch[v]) {
        calc(to);

        //maxd
        upd(maxd[v], maxd[to] + 1, _maxd[v], _maxd[to]);

        //sub_path
        upd(sub_path[v], sub_path[to], _sub_path[v], _sub_path[to]);

        //path1
        upd(path1[v], path1[to] + 1, _path1[v], _path1[to]);
    }

    //update sub_path[v]
    upd(sub_path[v], maxd[v], _sub_path[v], { v, _maxd[v] });
    sort(ch[v].begin(), ch[v].end(), [&](const int a, const int b) {return maxd[a] > maxd[b]; });
    if (ch[v].size() >= 2)
        upd(sub_path[v], maxd[ch[v][0]] + maxd[ch[v][1]] + 1, _sub_path[v], { _maxd[ch[v][0]], _maxd[ch[v][1]] });

    //update ans with 1 added edge
    upd_ans(maxd[v], { v, _maxd[v] });
    if (ch[v].size() >= 2)
        upd_ans(maxd[ch[v][0]] + maxd[ch[v][1]] + 1, { _maxd[ch[v][0]], _maxd[ch[v][1]] });

    //upate ans with 2 added edges
    if (ch[v].size() >= 2) {
        for (int i = 0; i < ch[v].size(); ++i) {
            int u1 = ch[v][i];
            int u2 = (i == 0 ? ch[v][1] : ch[v][0]);
            upd_ans(path1[u1] + maxd[u2] + 1, { _path1[u1].u1, _path1[u1].u2 }, { _path1[u1].last, _maxd[u2] });
        }
    }
    if (ch[v].size() >= 3) {
        for (int i = 0; i < ch[v].size(); ++i) {
            int u2 = ch[v][i];
            int u1 = (i == 0 ? ch[v][1] : ch[v][0]);
            int u3 = (i <= 1 ? ch[v][2] : ch[v][1]);
            upd_ans(maxd[u1] + sub_path[u2] + maxd[u3] + 1, { _maxd[u1], _sub_path[u2].first },
                { _sub_path[u2].second, _maxd[u3] });
        }
    }

    //update path1[v]
    if (ch[v].size() >= 2) {
        for (int i = 0; i < ch[v].size(); i++) {
            int maxi_to = ch[v][!i];
            int to = ch[v][i];

            pth cur = {_maxd[maxi_to], _sub_path[to].first, _sub_path[to].second};
            upd(path1[v], maxd[maxi_to] + sub_path[to] + 1, _path1[v], cur);
        }
    }

    //upate ans with 2 added edges
    if (ch[v].size() >= 1)
        upd_ans(path1[v], { _path1[v].u1, _path1[v].u2 }, { _path1[v].last, v });
}

void dfs(int v, int pr) {
    for (int to : g[v]) {
        if (to == pr) continue;
        ch[v].push_back(to);

        dfs(to, v);
    }
}

void input() {
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
}

void rand_gen() {
    for (int i = 0; i < MAX_N; i++) {
        g[i].clear();
        ch[i].clear();
    }
    ans = 0;
    memset(maxd, 0, sizeof(maxd));
    memset(path1, 0, sizeof(path1));
    memset(sub_path, 0, sizeof(sub_path));

    n = 50;

    for (int v = 1; v < n; v++) {
        int p = rand() % v;
        g[p].push_back(v);
        g[v].push_back(p);
    }
}

int main() {
    //input();
    srand(time(0));
    for (int cnt = 0;; ++cnt) {
        if (cnt && (cnt % 1000 == 0)) cout << '=';
        rand_gen();

        dfs(0, -1);

        calc(0);

        g[path[0].first].push_back(path[0].second);
        g[path[0].second].push_back(path[0].first);
        assert(path[0].first >= 0 && path[0].first < n);
        assert(path[0].second >= 0 && path[0].second < n);
        if (path[1].first != -1) {
            assert(path[1].first >= 0 && path[1].first < n);
            assert(path[1].second >= 0 && path[1].second < n);
            g[path[1].first].push_back(path[1].second);
            g[path[1].second].push_back(path[1].first);
        }

        int real_max_cycle = find_maxi_cycle();
        //cout << real_max_cycle << '\n';
        if (real_max_cycle != ans) {
            cout << '\n';

            cout << "real: " << real_max_cycle << '\n' <<
                "ans: " << ans;

            cout << n << '\n';
            for (int v = 0; v < n; v++) {
                cout << v << ": ";
                for (int u : ch[v]) cout << u << ' ';
                cout << '\n';
            }
            break;
        }
    }
    /*

    cout << ans << '\n';
    cout << path[0].first + 1 << ' ' << path[0].second + 1;
    if (path[1].first != -1)
        cout << '\n' << path[1].first + 1 << ' ' << path[1].second + 1;
        */
}