NN country

题目描述
传送门：http://codeforces.com/contest/983/problem/E

题解
首先有一个很显然的贪心策略，我们对于每个节点预处理出从它出发向上乘一次车最远能到哪。
对于一次询问，两个点x,y，我们先让这两个点贪心地往lca方向跑。
这样x点跑了a次到了lx点，y点跑了b次到了rx点。
如果lx到rx可以乘一次车到达，那么答案是a+b+1，否则答案就是a+b+2。
所以问题就转化成了给两个点x,y，询问它们的子树中是否存在可以直达的路径。
一种暴力办法是直接上树套树，树状数组套个set就好了，题目时限3秒，在cf上应该能过。
考虑少一个log的做法。
我们对于一组点lx,rx，它们对应的dfs序区间是 [L[lx],R[lx]] 和 [L[rx],R[rx]]。
先dfs一遍这棵树，对于每条巴士线路，当访问到它的起点的时候，将它的终点赋上权值。
如果我们将 [L[lx],R[lx]] 区间内出发的路径所对应的终点的权值扣回去之后 [L[rx],R[rx]] 的权值和扣回去之前不一样那么就存在一条可以直达的路径。
在写的时候，我们按dfs序跑一遍，一边跑一边修改。
我们在访问到L[lx]-1 和 R[lx]的时候分别求一下 [L[rx],R[rx]]的值，把它们相减判断一下就好了。
区间和拿个树状数组搞搞就好了。

代码

#include<bits/stdc++.h>
#define N 200005
#define D 18
using namespace std;
int n,m,Q,f[N][D+1],w[N][D+1],g[N],sum[N],ans[N];
int k,la[N],ff[N*2],dep[N],L[N],R[N],cnt,c[N];
struct node{int a,b;}e[N*2];
vector<node>q[N];
vector<int>t[N],h[N];
void add(int a,int b)
{e[++k]=(node){a,b};ff[k]=la[a];la[a]=k;e[++k]=(node){b,a};ff[k]=la[b];la[b]=k;
}class bit
{public:void modify(int x,int val){for(;x<=n;x+=x&-x)c[x]+=val;}int qry(int x){int res=0;for(;x;x-=x&-x)res+=c[x];return res;}
}T;void dfs1(int x)
{L[x]=++cnt;for(int i=1;i<=D;i++)w[x][i]=w[w[x][i-1]][i-1];for(int a=la[x];a;a=ff[a])if(e[a].b!=w[x][0])dep[e[a].b]=dep[x]+1,dfs1(e[a].b);R[x]=cnt;
}void dfs2(int x)
{g[x]=x;for(int i=0;i<h[x].size();i++)if(dep[h[x][i]]<dep[g[x]])g[x]=h[x][i];for(int a=la[x];a;a=ff[a])if(e[a].b!=w[x][0]){dfs2(e[a].b);if(dep[g[e[a].b]]<dep[g[x]])g[x]=g[e[a].b];}f[x][0]=g[x];
}void prepare()
{for(int j=1;j<=D;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
}int lca(int x,int y)
{if(dep[x]<dep[y])swap(x,y);for(int i=D;i>=0;i--)if(dep[w[x][i]]>=dep[y])x=w[x][i];if(x==y)return x;for(int i=D;i>=0;i--)if(w[x][i]!=w[y][i])x=w[x][i],y=w[y][i];return w[x][0];
}node work(int x,int pos)
{if(x==pos)return (node){x,0};int res=0;for(int i=D;i>=0;i--)if(dep[f[x][i]]>dep[pos])x=f[x][i],res+=(1<<i);if(f[x][0]==x)return (node){x,-1};return (node){x,res};
}int main()
{int x,y,id,inv,pos;node A,B;scanf("%d",&n);for(int i=2;i<=n;i++)scanf("%d",&w[i][0]),add(w[i][0],i);dep[1]=1;dfs1(1);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);pos=lca(x,y);if(L[x]>L[y])swap(x,y);t[L[x]].push_back(L[y]);if(dep[pos]<dep[x])h[x].push_back(pos);if(dep[pos]<dep[y])h[y].push_back(pos);}scanf("%d",&Q);dfs2(1);prepare();for(int i=1;i<=Q;i++){scanf("%d%d",&x,&y);pos=lca(x,y);A=work(x,pos);B=work(y,pos);if(A.b==-1||B.b==-1){ans[i]=-1;continue;}if(x==pos||y==pos){ans[i]=A.b+B.b+1;continue;}ans[i]=A.b+B.b+2;x=A.a;y=B.a;if(L[x]>L[y])swap(x,y);q[L[x]-1].push_back((node){y,-i});q[R[x]].push_back((node){y,i}); }for(int i=1;i<=n;i++){for(int j=0;j<t[i].size();j++)T.modify(t[i][j],1);for(int j=0;j<q[i].size();j++){inv=(q[i][j].b>0?1:-1);x=q[i][j].a;id=q[i][j].b*inv;sum[id]+=inv*(T.qry(R[x])-T.qry(L[x]-1)); }}for(int i=1;i<=Q;i++)printf("%d\n",ans[i]-(sum[i]>0));return 0;
}