Description
豪哥生活在一个 n 个点的树形城市里面,每一天都要走来走去。虽然走的是比较的 多,但是豪哥在这个城市里面的朋友并不是很多。 当某一天,猴哥给他展现了一下大佬风范之后,豪哥决定要获得一些交往机会来提升交 往能力。豪哥现在已经物色上了一条友,打算和它(豪哥并不让吃瓜群众知道性别)交 往。豪哥现在 spy 了一下这个人的所有行程起点和终点,豪哥打算从终点开始走到起点与 其相遇。但是豪哥是想找话题的,他想知道以前有多少次行程和此次行程是有交集的,这 样豪哥就可以搭上话了。这个路径与之前路径的有交集数量作为豪哥此次的交往机会。 但是豪哥急着要做交往准备,所以算什么交往机会的小事情就交给你了。
Solution
如果两条路径有交集,只可能是以下两种情况:
- 此条路径的lca在之前某条路径上
- 之前某条路径的lca在此条路径上
这两个情况有交集——两条路径的lca重合,所以统计答案时可以这样操作:
- 更新答案:
- 在A树中将此条路径的lca的子树全部+1
- 在B树中将此条路径两端点+1,lca-2
- 统计答案:
- 统计在A树中两端点到根的路径减去lca到根的路径上lca数量
- 统计在B树中lca的子树
- lca重合的情况特判
可以用树状数组处理
#include<iostream> #include<cstdio> using namespace std; int n,m,fa[200005][25],st[200005],ed[200005],cnt,dep[200005],sum[200005],ans,head[200005],tot; struct Edge { int to,nxt; }edge[400005]; int lowbit(int x) { return x&-x; } struct Tree { int tree[200005]; void add(int pos,int v) { while(pos<=n) { tree[pos]+=v; pos+=lowbit(pos); } } int query(int pos) { int ret=0; while(pos) { ret+=tree[pos]; pos-=lowbit(pos); } return ret; } }tr1,tr2; inline int read() { int f=1,w=0; char ch=0; while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<1)+(w<<3)+ch-'0'; ch=getchar(); } return f*w; } void dfs(int k,int f) { fa[k][0]=f; st[k]=++cnt; dep[k]=dep[f]+1; for(int i=1;i<=20;i++) { fa[k][i]=fa[fa[k][i-1]][i-1]; } for(int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if(v==f) { continue; } dfs(v,k); } ed[k]=cnt; } int lca(int x,int y) { if(dep[x]<dep[y]) { swap(x,y); } for(int i=20;i>=0;i--) { if(dep[fa[x][i]]>=dep[y]) { x=fa[x][i]; } } if(x==y) { return x; } for(int i=20;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } return fa[x][0]; } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); edge[++tot]=(Edge){v,head[u]}; head[u]=tot; edge[++tot]=(Edge){u,head[v]}; head[v]=tot; } dfs(1,0); m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),x=lca(u,v); printf("%d\n",tr1.query(st[v])+tr1.query(st[u])-2*tr1.query(st[x])+tr2.query(ed[x])-tr2.query(st[x]-1)+sum[x]); sum[x]++; tr1.add(st[x],1); tr1.add(ed[x]+1,-1); tr2.add(st[u],1); tr2.add(st[v],1); tr2.add(st[x],-2); } return 0; }相遇