正題

題目鏈接:https://www.51nod.com/Contest/Problem.html#contestProblemId=1150

---

題目大意

給出兩顆$n$個(gè)點(diǎn)的樹，求有多少個(gè)點(diǎn)$(i,j)$對(duì)使得在兩棵樹中$i$都是$j$的祖先。

---

解題思路

在$dfs$序中一個(gè)節(jié)點(diǎn)的孩子是在一個(gè)連續(xù)的區(qū)間中的。所以對(duì)于第一棵樹的每個(gè)節(jié)點(diǎn)的區(qū)間都作為詢問(wèn)，用莫隊(duì)進(jìn)行排序。

之后區(qū)間每次加入一個(gè)節(jié)點(diǎn)我們就在線段樹中給另一棵樹該節(jié)點(diǎn)對(duì)應(yīng)的$dfs$序位置$+1$，然后詢問(wèn)即可。

---

$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); }

總結(jié)

以上是生活随笔為你收集整理的51nod-猴猴的比赛【莫队,线段树】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。