D4T4 路径的交

Desciption：

给定一颗 $n$ 个节点的树，以及 $m$ 条路径，第 $i$ 条路径与前 $i-1$ 条有多少相交的（点相交即视为路径相交）

Solution:

现在有两条路径 $a$ 和 $b$ ，有两种情况，一种是 $a$ 的 $lca$ 在 $b$ 上，另一种是 $b$ 的 $lca$ 在 $a$ 上。

所以就转化成了两个问题：

  1. 当前路径上有几个之前的 $lca$

  2. 之前的路径有几个经过当前的 $lca$

可以用两个树状数组来维护，一个支持单点修改、链上查询，另一个支持链上修改、单点查询。

Code：

目前只能用倍增来跳 $lca$ ，用欧拉序跳的有点奇怪（悲

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
#define in read()
#define ll long long
const int inf=0x3f3f3f3f;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	} 
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar(); 
	}
	return x*f;
}
const int maxn=2e5+10;
struct edge{
	int u,v,nxt;
}e[maxn*10];
int cnt=0,h[maxn];
inline void add(int u,int v){
	e[++cnt]=(edge){u,v,h[u]};
	h[u]=cnt;
}
int n,m,u,v;
int val[maxn],st[maxn],ed[maxn],tim=0,dfn[maxn<<1],dep[maxn],fath[maxn];
int f[maxn<<1][24];
int mmin(int a,int b){
    return dep[a]<dep[b]?a:b;
};
void dfs(int u,int fa){
	st[u]=++tim;
	f[u][0]=fa;
	for(int i=1;i<19;++i) f[u][i]=f[f[u][i-1]][i-1];
	dep[u]=dep[fa]+1;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v!=fa) dfs(v,u);
	}
	ed[u]=tim;
}

int lca(int x,int y) {   
    if(dep[x]<dep[y]) swap(x,y);   
    for(int i=18;i>=0;i--) 
	  	if(dep[f[x][i]]>=dep[y]) x=f[x][i];   
    if(x==y) return x;   
    for(int i=18;i>=0;i--) 
	  	if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];    
    return f[x][0];   
}
struct bittree{
	int t[maxn],siz;
	inline int lowbit(int x){
		return x&(-x);
	}
	inline void update(int x,int val){
		while(x<=n){
			t[x]+=val;
			x+=lowbit(x);
		}
	}
	inline int query(int x){
		int res=0;
		while(x){
			res+=t[x];
			x-=lowbit(x);
		}
		return res;
	}
}t1,t2;
int clac(int x,int y,int lca){
	int ans=0;
	ans+=t1.query(ed[lca])-t1.query(st[lca]-1);
	ans+=t2.query(st[x])+t2.query(st[y])-t2.query(st[lca])*2;
	return ans;
}
int main(){
	n=in;
	for(int i=1;i<n;i++){
		u=in;v=in;
		add(u,v);add(v,u);
	}
	m=in;
	dfs(1,0);
	for(int i=1;i<=m;i++){
		u=in;v=in;
		int lcaa=lca(u,v);
		printf("%d\n",clac(u,v,lcaa)+val[lcaa]);
		val[lcaa]++;
		t1.update(st[u],1);
		t1.update(st[v],1);
		t1.update(st[lcaa],-2);
		t2.update(st[lcaa],1);
		t2.update(ed[lcaa]+1,-1);
	}
	return 0;
}