【題解】Codeforces 1528C. Trees of Tranquillity

【題目敘述】http://codeforces.com/contest/1528/problem/C

#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
const int maxn = 300005;
int t, n, a[maxn], b[maxn], in[maxn], out[maxn], idx, ans;
vector <int> va[maxn], vb[maxn];
set <pair<int, int> > st;
 
void f1(int x){
    idx++;
    in[x] = idx;
    for (int i:vb[x]){
        f1(i);
    }
    out[x] = idx;
}
 
void f2(int x){
    pair <int, int> p = {0, 0};
    if (st.empty()) st.insert({in[x], out[x]});
    else{
        auto it = st.upper_bound({in[x], out[x]});
        if (it == st.end() || (*it).first > out[x]){
            if (it != st.begin() && in[x] <= (*prev(it)).second){
                it--;
                p = *it;
                st.erase(it);
            }
            st.insert({in[x], out[x]});
        }
    }
    ans = max(ans, (int)st.size());
    for (int i:va[x]){
        f2(i);
    }
    st.erase({in[x], out[x]});
    if (p != make_pair(0, 0)) st.insert(p);
}
 
int main() {
    cin >> t;
    while (t--){
        cin >> n;
        for (int i = 1; i <= n; i++){
            va[i].clear();
            vb[i].clear();
        }
        for (int i = 2; i <= n; i++){
            cin >> a[i];
            va[a[i]].push_back(i);
        }
        for (int i = 2; i <= n; i++){
            cin >> b[i];
            vb[b[i]].push_back(i);
        }
        idx = 0;
        f1(1);
        st.clear();
        ans = 0;
        f2(1);
        cout << ans << "\n";
    }
}
分享本文 Share with friends