正题
题目链接:https://www.51nod.com/Contest/Problem.html#contestProblemId=1150
题目大意
给出两颗
n
n
n个点的树，求有多少个点
(
i
,
j
)
(i,j)
(i,j)对使得在两棵树中
i
i
i都是
j
j
j的祖先。
解题思路
在
d
f
s
dfs
dfs序中一个节点的孩子是在一个连续的区间中的。所以对于第一棵树的每个节点的区间都作为询问，用莫队进行排序。
之后区间每次加入一个节点我们就在线段树中给另一棵树该节点对应的
d
f
s
dfs
dfs序位置
+
1
+1
+1，然后询问即可。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std
;
const int N
=110000;
struct edge_node
{
int to
,next
;
}e1
[N
*2],e2
[N
*2];
struct tree_node
{
int l
,r
,w
,lazy
,num
;
};
struct ques_node
{
int l
,r
,id
,pos
;
}q
[N
];
bool cmp(ques_node x
,ques_node y
){
return x
.pos
<y
.pos
||(x
.pos
==y
.pos
&&x
.r
<y
.r
);
}
int n
,tot1
,tot2
,cnt
,w
,t
,ans
;
int dfn1
[N
],rfn1
[N
],ed1
[N
],ls1
[N
];
int dfn2
[N
],rfn2
[N
],ed2
[N
],ls2
[N
];
struct LineTree
{
tree_node t
[N
*4];
void Build(int x
,int l
,int r
)
{
t
[x
].l
=l
;t
[x
].r
=r
;
if(l
==r
)return;
int mid
=(l
+r
)/2;
Build(x
*2,l
,mid
);
Build(x
*2+1,mid
+1,r
);
}
int Ask(int x
,int l
,int r
)
{
if(t
[x
].l
==l
&&t
[x
].r
==r
)
return t
[x
].w
;
int mid
=(t
[x
].l
+t
[x
].r
)/2;
if(r
<=mid
) return Ask(x
*2,l
,r
);
if(l
>mid
) return Ask(x
*2+1,l
,r
);
return Ask(x
*2,l
,mid
)+Ask(x
*2+1,mid
+1,r
);
}
void Change(int x
,int pos
,int num
)
{
if(t
[x
].l
==t
[x
].r
)
{t
[x
].w
+=num
;return;}
if(pos
<=t
[x
*2].r
) Change(x
*2,pos
,num
);
else Change(x
*2+1,pos
,num
);
t
[x
].w
=t
[x
*2].w
+t
[x
*2+1].w
;
}
}Tree
;
void add1(int x
,int y
)
{
e1
[++tot1
].to
=y
;
e1
[tot1
].next
=ls1
[x
];
ls1
[x
]=tot1
;
}
void add2(int x
,int y
)
{
e2
[++tot2
].to
=y
;
e2
[tot2
].next
=ls2
[x
];
ls2
[x
]=tot2
;
}
void dp1(int x
,int fa
)
{
rfn1
[x
]=++cnt
;dfn1
[cnt
]=x
;
for(int i
=ls1
[x
];i
;i
=e1
[i
].next
){
int y
=e1
[i
].to
;
if(y
==fa
) continue;
dp1(y
,x
);
}
ed1
[x
]=cnt
;
}
void dp2(int x
,int fa
)
{
rfn2
[x
]=++cnt
;dfn2
[cnt
]=x
;
for(int i
=ls2
[x
];i
;i
=e2
[i
].next
){
int y
=e2
[i
].to
;
if(y
==fa
) continue;
dp2(y
,x
);
}
ed2
[x
]=cnt
;
}
int main()
{
scanf("%d",&n
);t
=sqrt(n
);
for(int i
=1;i
<n
;i
++){
int x
,y
;
scanf("%d%d",&x
,&y
);
add1(x
,y
);add1(y
,x
);
}
for(int i
=1;i
<n
;i
++){
int x
,y
;
scanf("%d%d",&x
,&y
);
add2(x
,y
);add2(y
,x
);
}
dp1(1,1);cnt
=0;dp2(1,1);
Tree
.Build(1,1,n
);
for(int i
=1;i
<=n
;i
++)
q
[i
].l
=rfn1
[i
],q
[i
].r
=ed1
[i
],q
[i
].id
=i
,q
[i
].pos
=(q
[i
].l
-1)/t
+1;
sort(q
+1,q
+1+n
,cmp
);
int l
=1,r
=0;
for(int i
=1;i
<=n
;i
++)
{
while(l
>q
[i
].l
)
Tree
.Change(1,rfn2
[dfn1
[--l
]],1);
while(r
<q
[i
].r
)
Tree
.Change(1,rfn2
[dfn1
[++r
]],1);
while(l
<q
[i
].l
)
Tree
.Change(1,rfn2
[dfn1
[l
++]],-1);
while(r
>q
[i
].r
)
Tree
.Change(1,rfn2
[dfn1
[r
--]],-1);
ans
+=Tree
.Ask(1,rfn2
[q
[i
].id
],ed2
[q
[i
].id
])-1;
}
printf("%d",ans
);
}
