Submission #1236155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236155		AlgorithmWarrior	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	207 ms	67600 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int const MAX=4e5+5;
int p[MAX];
int n;
vector<int>tree[MAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>p[i];
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        u=p[u];
        v=p[v];
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
}

int euler[MAX];
int pos[MAX];
int h[MAX];

void dfs(int nod,int tata){
    static int time=0;
    euler[++time]=nod;
    pos[nod]=time;
    for(auto fiu : tree[nod])
    if(fiu!=tata){
        h[fiu]=h[nod]+1;
        dfs(fiu,nod);
        euler[++time]=nod;
    }
}

int const LOG=20;
int rmq[MAX][LOG];
int loga[MAX];

void calc_rmq(){
    int i;
    for(i=1;i<2*n;++i)
        rmq[i][0]=euler[i];
    int j;
    for(j=1;j<LOG;++j)
    for(i=1;i<2*n;++i){
        rmq[i][j]=rmq[i][j-1];
        int nextpos=i+(1<<(j-1));
        if(nextpos<2*n && h[rmq[i][j]]>h[rmq[nextpos][j-1]])
            rmq[i][j]=rmq[nextpos][j-1];
    }
    for(i=2;i<MAX;++i)
        loga[i]=loga[i/2]+1;
}

int lca(int nod1,int nod2){
    int p1=pos[nod1];
    int p2=pos[nod2];
    if(p1>p2)
        swap(p1,p2);
    int len=p2-p1+1;
    int logar=loga[len];
    if(h[rmq[p1][logar]]<h[rmq[p2-(1<<logar)+1][logar]])
        return rmq[p1][logar];
    else
        return rmq[p2-(1<<logar)+1][logar];
}

int dist(int nod1,int nod2){
    return h[nod1]+h[nod2]-2*h[lca(nod1,nod2)];
}

struct DSU{
    int n;
    int tata[MAX];
    void init(int n){
        this->n=n;
    }
    int root(int nod){
        if(tata[nod]){
            int rt=root(tata[nod]);
            tata[nod]=rt;
            return rt;
        }
        return nod;
    }
    void uneste(int nod1,int nod2){
        int root1=root(nod1);
        int root2=root(nod2);
        tata[root2]=root1;
    }
}dsu;

long long ans[MAX];

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

void solve(){
    dsu.init(n);
    int i;
    for(i=1;i<=n;++i)
        for(auto vec : tree[i])
            if(vec<i){
                int rt=dsu.root(vec);
                maxself(ans[i],ans[rt]+dist(rt,i));
                dsu.uneste(i,rt);
            }
}

void write(long long ans){
    cout<<ans;
}

int main()
{
    read();
    dfs(1,0);
    calc_rmq();
    solve();
    write(ans[n]);
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26