题意：
思路：
update！！！我感觉这可能是括号序，大概不同的叫法吧，迷了
简化版本是询问区间[ l , r ]里不同数的个数，可以用莫队，树状数组，主席树多种方法做
将该问题搬到树上后，依旧可以用莫队求解
现在考虑怎么样将树上问题转化为序列问题，d f s序列，树链剖分等等
d f s序是行不通的，因为无法处理l c a的贡献
考虑欧拉序，即当访问到u时，将u加入序列；访问u的子树；回溯到u时，再将u加入序列；
记f i r s t [ x ]表示x在欧拉序第一次出现的下标，l a s [ x ]表示最后一次出现的下标
不妨设f i r s t [ x ] < f i r s t [ y ]
如果l c a ( x , y ) = = x的话，x − > y路径上的点就是区间[ f i r s t [ x ] , f i r s t [ y ] ]内的点
否则，就是[ l a s [ x ] , f i r s t [ y ] ]加上l c a ( x , y )
画图就可以验证，然后用莫队就可以啦。
代码
const int maxn=100010,mod=1e9+7,inf=0x3f3f3f3f; int fa[maxn][25], dep[maxn],w[maxn]; int e[maxn],ne[maxn],m; int h[maxn], idx = 0,n,root; vector<int>num; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void init() { memset(h, -1, sizeof h); idx = 0; } void bfs(int root) { queue<int>q; memset(dep, 0x3f, sizeof dep); dep[0] = 0; dep[root] = 1; q.push(root); while(!q.empty()) { int t = q.front(); q.pop(); for(int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if(dep[j] > dep[t] + 1) { dep[j] = dep[t] + 1; q.push(j); fa[j][0] = t; for(int k = 1; k <= 15; k++) fa[j][k] = fa[fa[j][k - 1]][k - 1]; } } } } int lca(int a, int b) { if(dep[a] < dep[b]) swap(a, b); for(int k = 15; k >= 0; k--) if(dep[fa[a][k]] >= dep[b]) a = fa[a][k]; if(a == b) return a; for(int k = 15; k >= 0; k--) if(fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k]; return fa[a][0]; } int seq[maxn],top,first[maxn],las[maxn]; void dfs(int u,int fa){ seq[++top]=u; first[u]=top; for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(j!=fa) dfs(j,u); } seq[++top]=u; las[u]=top; } struct node{ int id,l,r,p; }q[maxn]; int len,ans[maxn],res=0,st[maxn],cnt[maxn]; bool cmp(node a,node b){ if(a.l/len==b.l/len) return a.r<b.r; return a.l/len<b.l/len; } void add(int x){ //x=seq[x]; st[x]^=1; if(st[x]==0){ cnt[w[x]]--; if(!cnt[w[x]]) res--; } else{ if(!cnt[w[x]]) res++; cnt[w[x]]++; } } void del(int x){ x=seq[x]; st[x]^=1; if(st[x]==0){ cnt[w[x]]--; if(!cnt[w[x]]) res--; } else{ if(!cnt[w[x]]) res++; cnt[w[x]]++; } } int main(){ init(); n=read,m=read; rep(i,1,n) w[i]=read,num.push_back(w[i]); sort(num.begin(),num.end()); num.erase(unique(num.begin(),num.end()),num.end()); rep(i,1,n) w[i]=lower_bound(num.begin(),num.end(),w[i])-num.begin(); rep(i,1,n-1){ int u=read,v=read; add(u,v);add(v,u); } dfs(1,-1); bfs(1); rep(i,1,m){ int a=read,b=read; if(first[a]>first[b]) swap(a,b); int p=lca(a,b); if(a==p) q[i]={i,first[a],first[b]}; else q[i]={i,las[a],first[b],p}; } len=sqrt(top); sort(q+1,q+1+m,cmp); int nowl=1,nowr=0; rep(i,1,m){ int id=q[i].id,ql=q[i].l,qr=q[i].r,p=q[i].p; // cout<<id<<" "<<ql<<" "<<qr<<" "<<p<<endl; while(nowr<qr) add(seq[++nowr]); while(nowr>qr) add(seq[nowr--]); while(nowl<ql) add(seq[nowl++]); while(nowl>ql) add(seq[--nowl]); if(p) add(p); ans[id]=res; if(p) add(p); //rep(i,1,n) cout<<cnt[i]<<" "; //puts(""); } rep(i,1,m) cout<<ans[i]<<"\n"; return 0; }
