对于树上的路径询问问题
- O(1)的时间加入或删除一个点的贡献 -> \(O(n\sqrt n)\)的复杂度求出所有询问的答案
对树上的结点进行分块，离线询问后排序，顺序遍历暴力转移路径（转移时加入或删除路径上的点的贡献即可）。
关于转移路径：首先定义路径：设\(T_u\)为\(u\) 到根的路径上边的集合，那么\(u\)到\(v\) 的路径上的边的集合就是\(T_u \triangle T_v\) (\(\triangle\) 是对称差）。要从\(u\rightarrow v\) 转移到 \(u'\rightarrow v'\) 等价于
\[T_u \triangle T_v\rightarrow T_{u'}\triangle T_{v'} \]
根据对称差的性质\(T_u\triangle T_u\triangle T_{u'} = T_{u'}\) 所以只需要：
\[T_u \triangle T_v \triangle (T_u\triangle T_{u'})\triangle (T_v\triangle T_{v'}) = T_{u'}\triangle T_{v'}\]
体现在程序上就是从\(u\rightarrow v\) 转移到\(u' \rightarrow v'\)时，暴力遍历路径\(u\rightarrow u'\)和路径\(v\rightarrow v'\)上的边，如果一条边已经加入，那么删除它，如果没有加入，就加入它。这样就完成了对称差运算。
复杂度分析：设树分块大小为S，每次转移\(u\rightarrow u'\)在块内的转移路径长度是\(O(S)\)的，而\(v\rightarrow v'\)的转移可以按照\(dfs\)序来递增，这样复杂度就是\(O(ms+{n^2\over S})\)
当\(S=\sqrt n\)时最优
例题 题目传送门
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 40010;
const int M = 100010;
vector<int> G[N],alls;
int be[N],f[N][19],n,m,ans[M],dep[N],u=1,v=1,sum[N],vis[N],a[N],base,cnt;
int res;
int st[N],top;
struct Query{
int l,r;
int id;
}q[M];
void dfs(int x,int fa = -1){
for(int i=1;i<18;i++)
f[x][i] = f[f[x][i-1]][i-1];
int bottom = top;
for(int i = 0;i<G[x].size();i++){
int y = G[x][i];
if(y == fa)continue;
dep[y] = dep[x] + 1;
f[y][0] = x;
dfs(y,x);
if(top - bottom >= base){
cnt++;
while(top != bottom){
be[st[top--]] = cnt;
}
}
}
st[++top] = x;
}
bool cmp(Query a,Query b){
return be[a.l] == be[b.l] ? be[a.r] < be[b.r] : be[a.l] < be[b.l];
}
int LCA(int x,int y){
if(dep[x] > dep[y])swap(x,y);
for(int i=18;i>=0;i--)if(dep[x] <= dep[f[y][i]]) y = f[y][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];
}
void Run(int u){
if(vis[u] == 1){
vis[u] = 0;
if(--sum[a[u]] == 0)res--;
}
else{
vis[u] = 1;
if(sum[a[u]]++ == 0)res++;
}
}
void move(int x,int y){
if(dep[x] < dep[y])swap(x,y);
while(dep[x] > dep[y])Run(x),x = f[x][0];
while(x != y)Run(x),Run(y),x = f[x][0],y = f[y][0];
}
int main(){
scanf("%d%d",&n,&m);
base = sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
alls.push_back(a[i]);
}
/*离散化*/
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(int i=1;i<=n;i++){
int id = lower_bound(alls.begin(),alls.end(),a[i]) - alls.begin() + 1;
a[i] = id;
}
//存树
for(int i=1;i<n;i++){
int x,y;scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dep[1] = 1;//这里如果不单独设为wa
dfs(1);
while(top)be[st[top--]] = cnt;
//存询问
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id = i;
}
sort(q+1,q+1+m,cmp);
for(int i=1;i<=m;i++){
if(u != q[i].l){move(u,q[i].l);u=q[i].l;}
if(v != q[i].r){move(v,q[i].r);v=q[i].r;}
int anc = LCA(u,v);
Run(anc);//单独考虑LCA
ans[q[i].id] = res;
Run(anc);//
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}