Codeforces Round #483 (Div. 1) E. NN country 树上倍增 贪心 欧拉序
程序员文章站
2022-06-08 12:26:35
...
#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;
}
上一篇: PHP获取远路文件信息