Lvat_s Blog

怎么交都是RE

找来hzwer的程序RE

找来PoPoQQQ的程序RE

找来ww140142的程序RE

一开始我还以为自己写错了

毁我AC率

-------------------------

树上莫队

我没用王室联邦的分块方法，我写了一个块状树的版本

目前莫名RE

等我要到数据再修复……

-------------------------

本机怎么测都AC(Lemon)

以为是爆栈了写个手工栈照样RE

把数组放大10倍还是RE

不管了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=50005,M=100005,block_size=300,T=17;

int n,m,color[N],en,h[N],belong[N],cnt[N],dfn[N],indexs[N],colornum,dep[N],L,R,fa[N][20],Index,siz[N],block_cnt,ans[N],root;

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Edge{
int b,next;
}e[M];

struct Queries{
int l,r,a,b,id;
friend inline bool operator<(const Queries &A,const Queries &B){return belong[A.l]<belong[B.l] || (belong[A.l]==belong[B.l] && dfn[A.r]<dfn[B.r]);}
}que[M];

inline void AddEdge(const int &sa,const int &sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}

inline void Add(const int &x){cnt[x]++;if(cnt[x]==1)colornum++;}
inline void Del(const int &x){cnt[x]--;if(cnt[x]==0)colornum--;}
inline void Change(const int &x){if(indexs[x])Del(color[x]);else Add(color[x]);indexs[x]^=1;}

void dfs(int u,int f){
dfn[u]=++Index;fa[u][0]=f;
if(siz[belong[f]]==block_size)belong[u]=++block_cnt;
else belong[u]=belong[f];
siz[belong[u]]++;dep[u]=dep[f]+1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==f)continue;
    dfs(v,u);
}
}

inline void Prepare(){
for(register int i=1;i<=T;i++){
    for(register int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];
}
}

inline int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int deep=dep[u]-dep[v];
for(register int i=T;~i;i--)if(deep&(1<<i))u=fa[u][i];
for(register int i=T;~i;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return u==v?u:fa[u][0];
}

int main(){
freopen("3757.in","r",stdin);
freopen("3757.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++)Read(color[i]);
for(register int i=1;i<=n;i++){int u,v;Read(u);Read(v);if(u==0 || v==0)root=u+v;else AddEdge(u,v),AddEdge(v,u);}
dfs(root,0);
Prepare();
for(register int i=1;i<=m;i++){
    Read(que[i].l);Read(que[i].r);Read(que[i].a);Read(que[i].b);que[i].id=i;
    if(dfn[que[i].l]>dfn[que[i].r])swap(que[i].l,que[i].r);
}
sort(que+1,que+m+1);L=R=root;
for(register int i=1;i<=m;i++){
    int y=LCA(que[i].l,L);
	for(int j=que[i].l;j!=y;j=fa[j][0])Change(j);
	for(int j=L;j!=y;j=fa[j][0])Change(j);
	y=LCA(que[i].r,R);
	for(int j=que[i].r;j!=y;j=fa[j][0])Change(j);
	for(int j=R;j!=y;j=fa[j][0])Change(j);
	L=que[i].l;R=que[i].r;
    int x=LCA(L,R);
    Change(x);
    ans[que[i].id]=colornum;
    if(cnt[que[i].a] && cnt[que[i].b] && que[i].a!=que[i].b)ans[que[i].id]--;
    Change(x);
}
for(register int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}