相遇[dfs序][lca]

相遇[dfs序][lca]

豪哥生活在一个n个点的树形城市里面，每一天都要走来走去。虽然走的是比较的多，但是豪哥在这个城市里面的朋友并不是很多。

当某一天，猴哥给他展现了一下大佬风范之后，豪哥决定要获得一些交往机会来提升交往能力。豪哥现在已经物色上了一条友，打算和它（豪哥并不让吃瓜群众知道性别）交往。豪哥现在spy了一下这个人的所有行程起点和终点，豪哥打算从终点开始走到起点与其相遇。但是豪哥是想找话题的，他想知道以前有多少次行程和此次行程是有交集的，这样豪哥就可以搭上话了。这个路径与之前路径的有交集数量作为豪哥此次的交往机会。

但是豪哥急着要做交往准备，所以算什么交往机会的小事情就交给你了。

输入

第一行一个正整数n表示节点个数。接下来n-1行，每行两个正整数分别是u，v表示节点u和v之间有连边。接下来一行一个 正整数m表示路径个数。然后有m行，每行两个正整数分别是u，v分别表示u到v之间有一条路径

输出

输出共m行，每行一个整数，第i行表示豪哥在这条路径上获得的交往机会。

样例输入

5 1 2 1 3 3 4 3 5 4 4 5 4 2 1 3 1 2

样例输出

0 1 2 2

【数据范围与约定】

对于20%的数据n，m≤2000

对于另外20%的数据n，m≤50000

对于另外10%的数据n，m≤200000保证树形结构是一条链

对于另外50%的数据n，m≤200000

题意:求当前路径与之前多少条路径相交

分析:

[知识点1]: 路径(a,b) 与 路径(c,d) 相交

当且仅当 lca(a,b)在路径(c,d)上  或   lca(c,d)在路径(a,b)上

[知识点2]: dfs序维护 "单点修改, 路径查询""路径修改 , 单点查询"

也就是说,新来一条路径,我们需要查询之前lca落在这条路径上的个数  和   这个lca落在其它路径上的个数

第一个即为 "单点修改, 路径查询"

第二个也就成为 "路径修改 , 单点查询"

那不是我们熟悉的dfs序维护吗

对于"单点修改, 路径查询"

我们修改点时修改整棵子树 因为x的修改只对x的子树有贡献

查询分成3个  即 quary(x)+quary(y) - 2*quary(lca)

对于"路径修改 , 单点查询"

我们单点修改3个值(同上)

然后点的值即为它的子树和  因为子树的路径对它有贡献

巨佬cxr_o__o_cxr 的代码#includeusing namespace std;inline int read(){ int x=0;char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x;}struct edge{ int u,v,nxt;}e[800010];int first[400010],cnt=0;inline void add(int u,int v){ e[++cnt].u=u;e[cnt].v=v; e[cnt].nxt=first[u];first[u]=cnt;}int n,m;struct BIT{ int c[800010]={0}; inline void add(int x,int w){//x&-x —> x的二进制最右边的一个一的值 for(;x<=n;x+=x&-x)c[x]+=w; } inline int ask(int x){ int an=0; for(;x;x-=x&-x)an+=c[x]; return an; }}T1,T2;//T1区间修改单点查询 T2单点修改区间查询//T1别的路径的LCA在当前路径上(包括两个LCA相重）//T2当前路径的LCA在之前的路径上(不包括两个LCA相重） int fa[400010][20],dep[400010],st[400010],ed[400010],tim=0;void dfs(int x,int f){ st[x]=++tim;//dfs序 for(int i=1;(1<=0;--i) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i]; return fa[a][0];}int val[400010];int ans(int u,int v,int c){ int e=T1.ask(st[u])+T1.ask(st[v])-2*T1.ask(st[c])+val[c]; //cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。