题意

给定一棵树和若干条路线,每条路线相当于树上 x,y 之间的路径,途径路径上的每个点
给出若干个询问,每次询问从 u 到 v 至少需要利用几条路线
N,M,Q≤200000

题解

构建倍增数组g[i][j]表示从i点向上经过j条线路能到达的深度最小的点。
所以对于每一对询问的x,y,我们贪心地把它们提到深度大于等于lca地最大的点。记为x‘,y'然后判断是否有路径经过x’和y‘
然后各种情况特判(无解,x‘,y’为lca,有无路径经过x‘,y’)
然后对于判断是否路径经过x‘,y’。
可以用树状数组维护 DFS 序
DFS 遍历整棵树,递归进入 x 时,扫描路线 (x,y),把 y 在 DFS 序上对应位置 +1,
x,y 可直达,当且仅当 x 子树中的节点使 DFS 序上 y 对应区间的和发生了变化
(调了半天代码最后没调出来,最后屈辱地看了题解)
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int N=;
const int D=;
struct node{
int a,b;
};
vector<int> road[N],h[N];
vector<node> q[N];
int n,m,t,fa[N][D+],w[N][D+],head[N],sum[N],ans[N],g[N];
int cnt,tot,dep[N],id[N],size[N],c[N];
int lowbit(int x){
return x&-x;
}
void update(int x){
for(int i=x;i<=n;i+=lowbit(i)){
c[i]+=;
}
}
int check(int x){
int tmp=;
for(int i=x;i>=;i-=lowbit(i)){
tmp+=c[i];
}
return tmp;
}
struct edge{
int to,nxt;
}e[N*];
void add(int u,int v){
cnt++;
e[cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs1(int u,int deep){
dep[u]=deep;
id[u]=++tot;
size[u]=;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa[u][])continue;
dfs1(v,deep+);
size[u]+=size[v];
}
}
void dfs2(int u){
g[u]=u;
// cout<<u<<"ksdjfksdf"<<endl;
for(int i=;i<h[u].size();i++){
// cout<<h[u][i]<<endl;
if(dep[h[u][i]]<dep[g[u]])g[u]=h[u][i];
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
// cout<<v<<" "<<fa[u][0]<<endl;
if(v==fa[u][])continue;
dfs2(v);
if(dep[g[v]]<dep[g[u]])g[u]=g[v];
}
w[u][]=g[u];
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=D;i>=;i--){
if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
}
if(x==y)return x;
for(int i=D;i>=;i--){
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
}
return fa[x][];
}
node work(int x,int LCA){
if(x==LCA)return (node){x,};
int tmp=;
for(int i=D;i>=;i--)
if(dep[w[x][i]]>dep[LCA])x=w[x][i],tmp+=(<<i);
if(w[x][]==x)return (node){x,-};
return (node){x,tmp};
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&fa[i][]);
add(fa[i][],i);
add(i,fa[i][]);
}
dfs1(,);
for(int i=;i<=D;i++)
for(int j=;j<=n;j++){
fa[j][i]=fa[fa[j][i-]][i-];
}
scanf("%d",&m);
for(int i=;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
int c=lca(x,y);
// cout<<c<<endl;
if(id[x]>id[y])swap(x,y);
road[id[x]].push_back(id[y]);
if(dep[c]<dep[x])h[x].push_back(c);
if(dep[c]<dep[y])h[y].push_back(c);
}
dfs2();
for(int i=;i<=n;i++){
// cout<<g[i]<<endl;
}
for(int i=;i<=D;i++)
for(int j=;j<=n;j++){
w[j][i]=w[w[j][i-]][i-];
// cout<<w[j][i]<<endl;
}
scanf("%d",&t);
for(int i=;i<=t;i++){
int x,y;
scanf("%d%d",&x,&y);
int c=lca(x,y);
node A=work(x,c);
node B=work(y,c);
if(A.b==-||B.b==-){
ans[i]=-;
continue;
}
if(x==c||y==c){
ans[i]=A.b+B.b+;
continue;
}
ans[i]=A.b+B.b+;
x=A.a;
y=B.a;
if(id[x]>id[y])swap(x,y);
q[id[x]-].push_back((node){y,-i});
q[id[x]+size[x]-].push_back((node){y,i});
}
for(int i=;i<=n;i++){
for(int j=;j<road[i].size();j++)update(road[i][j]);
for(int j=;j<q[i].size();j++){
int num=(q[i][j].b>?:-);
int x=q[i][j].a;int y=q[i][j].b*num;
sum[y]+=num*(check(id[x]+size[x]-)-check(id[x]-));
}
}
for(int i=;i<=t;i++){
printf("%d\n",ans[i]-(sum[i]>));
}
return ;
}

最新文章

  1. wireshark 相关提示
  2. [leetcode] 题型整理之字符串处理
  3. office 2016 专业增强版 和 visio 2016 专业版 下载安装(附带激活工
  4. JMS【二】--ActiveMQ简单介绍以及安装
  5. ajax接触
  6. Codeforces Round #377 (Div. 2) A B C D 水/贪心/贪心/二分
  7. 《RESTful Web Services》第一章 使用统一接口
  8. Eclipse插件Mylyn管理上下文任务管理
  9. Python super() 函数的概念和例子
  10. Codeforces Round #426 Div. 1
  11. linux环境下安装qt过程
  12. FlashDevelop关闭分号自动格式化
  13. [转]我的MYSQL学习心得(六) 函数
  14. jQuery获得元素位置offset()和position()的区别
  15. mysql非安装包安装教程
  16. rails应用页面导出为pdf文档
  17. C#.NET中Dns类的常用方法及说明
  18. JMeter远程分布式联机性能测试
  19. Centos6安装SGE以及集群配置
  20. hello spring boot neo4j

热门文章

  1. navigator.clipboard 浏览器原生剪贴板
  2. 并发设计模式之Guarded Suspension模式
  3. 路飞学城Python-Day16
  4. 查看Linux 服务器是 32位还是64位的
  5. 洛谷 P1088 火星人 (全排列)
  6. java 实现顺序结构线性列表
  7. linux进程管理之进程创建(三)
  8. 【codeforces 335A】Banana
  9. Apache activemq入门示例(maven项目)
  10. 【递推DP】POJ1163The Triangle