Submission #1346976

#TimeUsernameProblemLanguageResultExecution timeMemory
1346976MMihalevTourism (JOI23_tourism)C++20
0 / 100
5093 ms12264 KiB
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

const int MAX_N=1e5+5;
const int LOG=17;

int n,m,q;
vector<int>g[MAX_N];
int c[MAX_N];
int parent[MAX_N][LOG];
int depth[MAX_N];
int T;
int in[MAX_N];
int out[MAX_N];

void dfs(int u,int par)
{
    in[u]=++T;

    parent[u][0]=par;
    for(int j=1;j<LOG;j++)
    {
        parent[u][j]=parent[parent[u][j-1]][j-1];
    }

    for(int v:g[u])
    {
        if(v==par)continue;

        depth[v]=depth[u]+1;
        dfs(v,u);
    }

    out[u]=T;
}

int lca(int u,int v)
{
    if(depth[v]<depth[u])swap(u,v);

    for(int j=LOG-1;j>=0;j--)
    {
        if(depth[v]-(1<<j)>=depth[u])
        {
            v=parent[v][j];
        }
    }

    if(u==v)return u;

    for(int j=LOG-1;j>=0;j--)
    {
        if(parent[u][j]!=parent[v][j])
        {
            u=parent[u][j];
            v=parent[v][j];
        }
    }

    return parent[u][0];
}

bool vis[MAX_N];
int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1,0);

    for(int i=1;i<=m;i++)
    {
        cin>>c[i];
    }

    vector<int>v,s,order;
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;

        v.clear();order.clear();s.clear();
        int ans=1;
        for(int id=l;id<=r;id++)
        {
            int u=c[id];

            if(vis[u])continue;
            v.push_back(u);
            vis[u]=1;
            order.push_back(u);
        }

        sort(order.begin(),order.end(),[](int u,int v)
    {
        return in[u]<in[v];
    });

        for(int i=1;i<order.size();i++)
        {
            int lc=lca(order[i-1],order[i]);
            ans+=depth[order[i]]-depth[lc];
            if(vis[lc])continue;
            v.push_back(lc);
            vis[lc]=1;
        }

        /*sort(v.begin(),v.end(),[](int u,int v)
    {
        return in[u]<in[v];
    });

        for(int&u:v)
        {
            while(s.size() && !(in[s.back()]<=in[u] && in[u]<=out[s.back()]))s.pop_back();
        
            if(s.size())
            {
                ans+=depth[u]-depth[s.back()];
            }

            s.push_back(u);
        }*/

        for(int u:v)vis[u]=0;

        cout<<ans<<"\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...