本文主要是介绍SPOJ Count on a tree II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给定一个n个节点的树，每个节点表示一个整数，问u到v的路径上有多少个不同的整数。
分析：树上莫队模板题，利用欧拉序将树上路径转化为序列，注意我们询问的区间长度为2∗N，所以预处理的时候一定要循环到2∗N。
参考博客：https://www.cnblogs.com/zwfymqz/p/9223425.html
https://blog.csdn.net/qq_39759315/article/details/88553210
代码：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int N=4e5+10;
struct node{int l,r,id,add,ans;
}q[N];
int n,m,tot,num,blo,ans,cnt[N],dep[N],v[N],s[N*2],t[N*2],pot[N*2],fa[N][25],ver[N],Next[N],lin[N],a[N],b[N];
///s数组为入dfs序（第一次） t数组为出dfs序（第二次）
///离散化 减小数值
void discrete(){sort(b+1,b+n+1);for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+n+1,a[i])-b;
}
///dfs求出 s t pot fa 为求lca做准备
void dfs(int x,int f){fa[x][0]=f,s[x]=++num,pot[num]=x;rep(i,1,20)if((1<<i)<=dep[x])fa[x][i]=fa[fa[x][i-1]][i-1];for(int i=lin[x];i;i=Next[i]){int y=ver[i];if(y==f)continue;dep[y]=dep[x]+1;dfs(y,x);}t[x]=++num,pot[num]=x;
}
///最近公共祖先
int lca(int x,int y){if(dep[x]<dep[y])swap(x,y);per(i,20,0)if((1<<i)<=dep[x]-dep[y])x=fa[x][i];if(x==y)return x;per(i,20,0)if(fa[x][i]!=fa[y][i]){x=fa[x][i],y=fa[y][i];}return fa[x][0];
}
void add(int x,int y){ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;}
bool cmp(node a,node b){return (a.l/blo==b.l/blo&&a.r<b.r)||(a.l/blo<b.l/blo);}
bool CMP(node a,node b){return a.id<b.id;}
void upd(int x){x=a[x];++cnt[x];if(cnt[x]==1) ans++;}
void del(int x){x=a[x];--cnt[x];if(cnt[x]==0) ans--;}
void update(int x){(v[x]) ? del(x):upd(x);v[x]^=1;}
int main(){scanf("%d%d",&n,&m);blo=sqrt(n);rep(i,1,n)scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+n+1);rep(i,1,n)a[i]=lower_bound(b+1,b+n+1,a[i])-b;int x,y;rep(i,2,n){scanf("%d%d",&x,&y);add(x,y),add(y,x);}dfs(1,1);rep(i,1,m){scanf("%d%d",&x,&y);int top=lca(x,y);if(s[x]>s[y])swap(x,y);if(x==top)q[i].l=s[x],q[i].r=s[y],q[i].id=i;else q[i].l=t[x],q[i].r=s[y],q[i].id=i,q[i].add=top;}sort(q+1,q+m+1,cmp);int l=1,r=0;for(int i=1;i<=m;++i){while(l<q[i].l) update(pot[l++]);while(l>q[i].l) update(pot[--l]);while(r<q[i].r) update(pot[++r]);while(r>q[i].r) update(pot[r--]);if(q[i].add) update(q[i].add);q[i].ans=ans;if(q[i].add) update(q[i].add);}sort(q+1,q+m+1,CMP);for(int i=1;i<=m;++i) printf("%d\n",q[i].ans);return 0;
}
这篇关于SPOJ Count on a tree II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
