北京免费网站建设模板下载,邯郸网站制作地方,长沙建站费用,dede自适应网站模板正题
题目链接:https://www.51nod.com/Contest/Problem.html#contestProblemId1150 题目大意
给出两颗nnn个点的树#xff0c;求有多少个点(i,j)(i,j)(i,j)对使得在两棵树中iii都是jjj的祖先。 解题思路
在dfsdfsdfs序中一个节点的孩子是在一个连续的区间中的。所以对于第一…正题
题目链接:https://www.51nod.com/Contest/Problem.html#contestProblemId1150 题目大意
给出两颗nnn个点的树求有多少个点(i,j)(i,j)(i,j)对使得在两棵树中iii都是jjj的祖先。 解题思路
在dfsdfsdfs序中一个节点的孩子是在一个连续的区间中的。所以对于第一棵树的每个节点的区间都作为询问用莫队进行排序。
之后区间每次加入一个节点我们就在线段树中给另一棵树该节点对应的dfsdfsdfs序位置111然后询问即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includeiostream
#includecmath
using namespace std;
const int N110000;
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.posy.pos||(x.posy.posx.ry.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].ll;t[x].rr;if(lr)return;int mid(lr)/2;Build(x*2,l,mid);Build(x*21,mid1,r);}int Ask(int x,int l,int r){if(t[x].llt[x].rr)return t[x].w;int mid(t[x].lt[x].r)/2;if(rmid) return Ask(x*2,l,r);if(lmid) return Ask(x*21,l,r);return Ask(x*2,l,mid)Ask(x*21,mid1,r); }void Change(int x,int pos,int num){if(t[x].lt[x].r){t[x].wnum;return;}if(post[x*2].r) Change(x*2,pos,num);else Change(x*21,pos,num);t[x].wt[x*2].wt[x*21].w;}
}Tree;
void add1(int x,int y)
{e1[tot1].toy;e1[tot1].nextls1[x];ls1[x]tot1;
}
void add2(int x,int y)
{e2[tot2].toy;e2[tot2].nextls2[x];ls2[x]tot2;
}
void dp1(int x,int fa)
{rfn1[x]cnt;dfn1[cnt]x;for(int ils1[x];i;ie1[i].next){int ye1[i].to;if(yfa) continue;dp1(y,x);}ed1[x]cnt;
}
void dp2(int x,int fa)
{rfn2[x]cnt;dfn2[cnt]x;for(int ils2[x];i;ie2[i].next){int ye2[i].to;if(yfa) continue;dp2(y,x);}ed2[x]cnt;
}
int main()
{scanf(%d,n);tsqrt(n);for(int i1;in;i){int x,y;scanf(%d%d,x,y);add1(x,y);add1(y,x);}for(int i1;in;i){int x,y;scanf(%d%d,x,y);add2(x,y);add2(y,x);}dp1(1,1);cnt0;dp2(1,1);Tree.Build(1,1,n);for(int i1;in;i)q[i].lrfn1[i],q[i].red1[i],q[i].idi,q[i].pos(q[i].l-1)/t1;sort(q1,q1n,cmp);int l1,r0;for(int i1;in;i){while(lq[i].l) Tree.Change(1,rfn2[dfn1[--l]],1);while(rq[i].r) Tree.Change(1,rfn2[dfn1[r]],1);while(lq[i].l) Tree.Change(1,rfn2[dfn1[l]],-1);while(rq[i].r) Tree.Change(1,rfn2[dfn1[r--]],-1);ansTree.Ask(1,rfn2[q[i].id],ed2[q[i].id])-1;}printf(%d,ans);
}
