#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _for(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define For(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
#define INF 0x7fffffff
#define il inline
#define rg register
const int N=2e5+5,M=2e5+5;
int n,m,len;
int pos[N];
int tot,head[N];
class Edge{
public:
int to,next;
}e[N<<1];
il void add(rg int u,rg int v){ e[++tot].to=v, e[tot].next=head[u], head[u]=tot; }
int cnt;
int w[N],b[N],st[N],ed[N],son[N],fa[N],siz[N],dep[N],top[N];
int ord[N<<1];
il void dfs1(rg int p,rg int q){
fa[p]=q, dep[p]=dep[q]+1, siz[p]=1, ord[++cnt]=p, st[p]=cnt;
int owo(-1);
for(rg int i=head[p];i;i=e[i].next){
rg int o(e[i].to);
if(o==q) continue;
dfs1(o,p);
siz[p]+=siz[o];
if(siz[o]>owo){
owo=siz[o];
son[p]=o;
}
}
ord[++cnt]=p, ed[p]=cnt;
}
il void dfs2(rg int p,rg int q){
top[p]=q;
if(!son[p]) return ;
dfs2(son[p],q);
for(rg int i=head[p];i;i=e[i].next){
rg int o(e[i].to);
if(o==fa[p] or o==son[p]) continue;
dfs2(o,o);
}
}
il int get_lca(rg int p,rg int q){
while(top[p]!=top[q]){
if(dep[top[p]]<dep[top[q]]) swap(p,q);
p=fa[top[p]];
}
if(dep[p]>dep[q]) swap(p,q);
return p;
}
class Query{
public:
int l,r,lca,id;
il bool operator < (const Query &p)const{ return (pos[l]^pos[p.l]) ? pos[l]<pos[p.l] : (pos[l]&1) ? r<p.r : r>p.r; }
}q[M];
bool vis[N];
int mem[N];
int res,ans[M];
il void work(rg int o){
vis[o] ? res-= ! --mem[w[o]] : res+= !mem[w[o]] ++;
vis[o]^=1;
}
int main(){
srand(time(NULL));
scanf("%d%d",&n,&m); len=sqrt(n);
_for(i,1,n) scanf("%d",&w[i]), b[i]=w[i], pos[i]=(i-1)/len+1;
sort(b+1,b+n+1);
int awa=unique(b+1,b+n+1)-(b+1);
_for(i,1,n) w[i]=lower_bound(b+1,b+awa+1,w[i])-b;
_for(i,1,n-1){
int u,v; scanf("%d%d",&u,&v);
add(u,v), add(v,u);
}
int root=1LL*rand()*rand()%n+1;
dfs1(root,0), dfs2(root,root);
_for(i,1,m){
int u,v; scanf("%d%d",&u,&v);
int lca=get_lca(u,v);
if(st[u]>st[v]) swap(u,v);
if(u==lca) q[i].l=st[u], q[i].r=st[v];
else q[i].l=ed[u], q[i].r=st[v], q[i].lca=lca;
q[i].id=i;
}
sort(q+1,q+m+1);
int l(1),r(0);
_for(i,1,m){
while(l>q[i].l) work(ord[--l]);
while(r<q[i].r) work(ord[++r]);
while(l<q[i].l) work(ord[l++]);
while(r>q[i].r) work(ord[r--]);
if(q[i].lca) work(q[i].lca);
ans[q[i].id]=res;
if(q[i].lca) work(q[i].lca);
}
_for(i,1,m) printf("%d\n",ans[i]);
return 0;
}
标签:int,work,pos,拓展,rg,il,研讨,lca,树上
From: https://www.cnblogs.com/Chanter/p/18222081