欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #483 (Div. 1) E. NN country 树上倍增 贪心 欧拉序

程序员文章站 2022-06-08 12:26:35
...

Codeforces Round #483 (Div. 1) E. NN country 树上倍增 贪心 欧拉序
Codeforces Round #483 (Div. 1) E. NN country 树上倍增 贪心 欧拉序

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<map>
#include<set>
using namespace std;

typedef double db;
typedef long long ll;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=10*x+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}

const int N=200100,inf=0X3f3f3f3f;

int last[N],ecnt;
struct EDGE{int to,nt;}e[N];
inline void add(int u,int v)
{e[++ecnt]=(EDGE){v,last[u]};last[u]=ecnt;}

int n;

int dep[N],anc[N][20],low[N][20];

int time_in[N],time_out[N],tim;

// get euler_tour
void dfs(int u)
{
    time_in[u]=++tim;
    for(int i=1;(1<<i)<=dep[u];++i)
        anc[u][i]=anc[anc[u][i-1]][i-1];
    for(int i=last[u];i;i=e[i].nt) dfs(e[i].to);
    time_out[u]=tim;
}

inline int getlca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    int len=dep[u]-dep[v];
    for(int i=0;(1<<i)<=len;++i)
        if((1<<i)&len) u=anc[u][i];
    if(u==v) return u;
    for(int i=18;~i;--i)
        if(anc[u][i]!=anc[v][i])
            u=anc[u][i],v=anc[v][i];
    return anc[u][0];
}

inline void update(int &x,int y)
{if(dep[y]<dep[x]) x=y;}

struct node
{
    int x,y,pos;

    friend bool operator <(const node &a,const node &b)
    {return a.x==b.x ? a.pos<b.pos : a.x<b.x;}
}q[N<<3];

int tot;

int bit[N];

inline void modify(int x)
{for(;x<=n;x+=(x&-x)) bit[x]++;}

inline int query(int x)
{
    int res(0);
    for(;x;x-=(x&-x)) res+=bit[x];
    return res;
}

int ans[N],cur[N];
bool book[N];

int main()
{
    n=read();int m,Q;
    register int i,j,u,v,grd;
    for(i=2;i<=n;++i)
        u=anc[i][0]=read(),
        dep[i]=dep[u]+1,add(u,i);
    dfs(1);

    m=read();
    for(i=1;i<=n;++i) low[i][0]=i;
    for(i=1;i<=m;++i)
        u=read(),v=read(),grd=getlca(u,v),
        update(low[u][0],grd),
        update(low[v][0],grd),
        q[++tot]=(node){time_in[u],time_in[v],-inf},
        q[++tot]=(node){time_in[v],time_in[u],-inf};


    for(i=n;i>1;--i) update(low[anc[i][0]][0],low[i][0]);
    for(i=1;i<=18;++i)
        for(u=1;u<=n;++u)
            low[u][i]=low[low[u][i-1]][i-1];
    Q=read();
    for(i=1;i<=Q;++i)
    {
        u=read(),v=read(),grd=getlca(u,v);

        if(dep[low[u][18]]>dep[grd] || dep[low[v][18]]>dep[grd])
        {ans[i]=-1;continue ;}

        for(j=18;~j;--j)
            if(dep[low[u][j]]>dep[grd])
                u=low[u][j],ans[i]+=1<<j;
        for(j=18;~j;--j)
            if(dep[low[v][j]]>dep[grd])
                v=low[v][j],ans[i]+=1<<j;

        if(u==grd || v==grd)
        {ans[i]++;continue ;}
        book[i]=1;
        q[++tot]=(node){time_in[u]-1,time_in[v]-1,i};
        q[++tot]=(node){time_in[u]-1,time_out[v],-i};
        q[++tot]=(node){time_out[u],time_in[v]-1,-i};
        q[++tot]=(node){time_out[u],time_out[v],i};
    }

    sort(q+1,q+1+tot);

    for(i=1;i<=tot;++i)
        if(q[i].pos==-inf) modify(q[i].y);
        else q[i].pos>0 ? cur[q[i].pos]+=query(q[i].y) : cur[-q[i].pos]-=query(q[i].y);

    for(i=1;i<=Q;++i)
    {
        if(cur[i]) ans[i]++;
        else if(book[i]) ans[i]+=2;
        print(ans[i]),puts("");
    }

    return 0;
}