https://www.luogu.org/problemnew/show/P3603
https://www.lydsy.com/JudgeOnline/problem.php?id=4763
就是先树分块，取所有的块顶为关键点
那么任意点与它祖先中离它最近的关键点的距离为根号级别
先预处理出任意两个关键点之间的路径上有的值的bitset
(vv[i][j][k]表示i到j的路径上是否出现值k)
那么，只需要在询问时，对于路径(a,b)，得到它路径上有的值的bitset；对于每个询问，把所有得到的bitset或一下就行了
得到bitset的方法见代码。。。
复杂度：n*(sqrt(n)+30000/32)
以下代码常数超大！为了卡常特意手写了bitset，还把块大小改到550（不是根号，实测这样更快...）
#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int n,m,F;
vector<int> e[];
int dd[];
const int bsz=;
ull lft[];
void init()
{
lft[]=;
for(int i=;i<;i++) lft[i]=lft[i-]<<;
}
struct bs
{
ull d[bsz];
int _Find_first_zero()
{
for(int i=;i<bsz;i++)
if(d[i]!=0xffffffffffffffff)
return (i<<)+__builtin_ffsll(~d[i])-;
}
void reset()
{
for(int i=;i<bsz;i++) d[i]=;
}
void set(int p,bool q=)
{
if(q) d[p>>]|=lft[p-((p>>)<<)];
else d[p>>]&=~lft[p-((p>>)<<)];
}
int count()
{
int ans=;
for(int i=;i<bsz;i++) ans+=__builtin_popcountll(d[i]);
return ans;
}
bs &operator|=(const bs &b)
{
for(int i=;i<bsz;i++) d[i]|=b.d[i];
return *this;
}
};
int bl[],rt[],cnt;
const int sz=;
namespace GBLOCK
{
int st[],tp;
void dfs(int u,int fa)
{
int i,ltp=tp;
for(i=;i<e[u].size();i++)
if(e[u][i]!=fa)
{
dfs(e[u][i],u);
if(tp-ltp>=sz)
{
rt[++cnt]=u;
while(tp!=ltp) bl[st[tp--]]=cnt;
}
}
st[++tp]=u;
}
void work()
{
dfs(,);
++cnt;rt[cnt]=;
while(tp) bl[st[tp--]]=cnt;
}
}
namespace LCA
{
int anc[][],dep[],l2n=;
void dfs(int u,int fa)
{
int i;
anc[u][]=fa;
dep[u]=dep[fa]+;
for(i=;i<=l2n;i++)
anc[u][i]=anc[anc[u][i-]][i-];
for(i=;i<e[u].size();i++)
if(e[u][i]!=fa)
dfs(e[u][i],u);
}
int lca(int x,int y)
{
int t,i;
if(dep[x]<dep[y]){t=x;x=y;y=t;}
for(t=dep[x]-dep[y],i=;t>;t>>=,i++)
if(t&) x=anc[x][i];
if(x==y) return x;
for(i=l2n;i>=;i--)
if(anc[x][i]!=anc[y][i])
{
x=anc[x][i];
y=anc[y][i];
}
return anc[x][];
}
}
using LCA::lca;
using LCA::dep;
using LCA::anc;
int nn[],nnn;
bs vv[][];//vv[i][j]:rt[i],rt[j]间答案
int num[];bs vis;
namespace PRE
{
int s;
void dfs(int u,int fa)
{
int i;
if(!num[dd[u]]) vis.set(dd[u]);
++num[dd[u]];
if(nn[u]) vv[s][nn[u]]=vis;
for(i=;i<e[u].size();i++)
if(e[u][i]!=fa)
dfs(e[u][i],u);
--num[dd[u]];
if(!num[dd[u]]) vis.set(dd[u],);
}
void work()
{
int i;
for(i=;i<=cnt;i++)
if(!nn[rt[i]])
nn[rt[i]]=++nnn;
for(i=;i<=n;i++)
if(nn[i])
{
s=nn[i];
dfs(i,);
}
}
}
bs tt;
void jump1(int &x,int ed)
{
if(ed==-) ed=rt[bl[x]];
while(x!=ed)
{
tt.set(dd[x]);
x=anc[x][];
}
tt.set(dd[x]);
}
void jump2(int &x,int ed)
{
int x1=x;
while(x1!=&&dep[rt[bl[x1]]]>=dep[ed]) x1=rt[bl[x1]];
tt|=vv[nn[x]][nn[x1]];
x=x1;
}
int main()
{ init();
int i,a,b,a1,a2,t,lans=,l;
scanf("%d%d%d",&n,&m,&F);
for(i=;i<=n;i++) scanf("%d",&dd[i]);
for(i=;i<n;i++)
{
scanf("%d%d",&a,&b);
e[a].pb(b);e[b].pb(a);
}
GBLOCK::work();LCA::dfs(,);PRE::work();
while(m--)
{
scanf("%d",&t);tt.reset();
for(i=;i<=t;i++)
{
scanf("%d%d",&a,&b);
if(F) a^=lans,b^=lans;
l=lca(a,b);
if(a!=&&dep[rt[bl[a]]]>=dep[l]) jump1(a,-);
if(b!=&&dep[rt[bl[b]]]>=dep[l]) jump1(b,-);
jump2(a,l);
jump2(b,l);
jump1(a,l);jump1(b,l);
}
a1=tt.count();
a2=tt._Find_first_zero();
printf("%d %d\n",a1,a2);
lans=a1+a2;
}
return ;
}
此方法相比直接分块然后处理边角，常数还是算小的，能够比bzoj2589https://www.cnblogs.com/hehe54321/p/9463519.html里面的做法快，但是还是过不去...
失败代码：
#pragma GCC optimize(3)
//#pragma GCC target("sse3","sse2","sse")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef pair<int,int> pii;
char B[<<],*SS=B;
#define getchar() (*SS++)
template<typename T>
inline void read(T &x)
{
x=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
x*=f;
}
int n,m;
struct E
{
int to,nxt;
}e[];
int f1[],ne;
int dd[];
int r[];
const int bsz=;
ul lft[];
void init()
{
lft[]=;
for(int i=;i<;i++) lft[i]=lft[i-]<<;
}
struct bs
{
ul d[bsz];
void reset(){memset(d,,sizeof(d));}
void set(int p,bool q=)
{
if(q) d[p>>]|=lft[p&];
else d[p>>]&=~lft[p&];
}
int count()
{
int ans=;
for(int i=;i<bsz;i++) ans+=__builtin_popcount(d[i]);
return ans;
}
bs &operator|=(const bs &b)
{
for(int i=;i<bsz;i++) d[i]|=b.d[i];
return *this;
}
};
int bl[],rt[],cnt;
const int sz=;
namespace GBLOCK
{
int st[],tp;
void dfs(int u,int fa)
{
int i,ltp=tp;
for(i=f1[u];i;i=e[i].nxt)
if(e[i].to!=fa)
{
dfs(e[i].to,u);
if(tp-ltp>=sz)
{
rt[++cnt]=u;
while(tp!=ltp) bl[st[tp--]]=cnt;
}
}
st[++tp]=u;
}
void work()
{
dfs(,);
++cnt;rt[cnt]=;
while(tp) bl[st[tp--]]=cnt;
}
}
namespace LCA
{
int anc[][],dep[],l2n=;
void dfs(int u,int fa)
{
int i;
anc[u][]=fa;
dep[u]=dep[fa]+;
for(i=;i<=l2n;i++)
anc[u][i]=anc[anc[u][i-]][i-];
for(i=f1[u];i;i=e[i].nxt)
if(e[i].to!=fa)
dfs(e[i].to,u);
}
int lca(int x,int y)
{
int t,i;
if(dep[x]<dep[y]){t=x;x=y;y=t;}
for(t=dep[x]-dep[y],i=;t>;t>>=,i++)
if(t&) x=anc[x][i];
if(x==y) return x;
for(i=l2n;i>=;i--)
if(anc[x][i]!=anc[y][i])
{
x=anc[x][i];
y=anc[y][i];
}
return anc[x][];
}
}
using LCA::lca;
using LCA::dep;
using LCA::anc;
int nn[],nnn,nn1[];
bs vvv[];int mem;
int vv[][];//vv[i][j]:rt[i],rt[j]间答案
bs vis;
namespace TTT
{
int anr[][],l2n=;
int dnn1[];
void work()
{
int i,j;
for(i=;i<=nnn;i++) anr[i][]=nn[r[nn1[i]]];
//puts("anr");
//for(i=1;i<=nnn;i++) printf("%d ",anr[i][0]);
//puts("");
//return;
for(j=;j<=l2n;j++)
for(i=;i<=nnn;i++)
anr[i][j]=anr[anr[i][j-]][j-];
for(i=;i<=nnn;i++) dnn1[i]=dep[nn1[i]];
}
}
using TTT::anr;
using TTT::dnn1;
namespace PRE
{
void work()
{
int i,j;
for(i=;i<=cnt;i++)
if(!nn[rt[i]])
nn[rt[i]]=++nnn,nn1[nnn]=rt[i];
for(i=;i<=n;i++)
if(nn[i])
{
vis.reset();
j=i;
vis.set(dd[j]);
while(j!=)
{
j=anc[j][];
vis.set(dd[j]);
if(nn[j]) vvv[vv[nn[i]][nn[j]]=++mem]=vis;
}
}
}
}
bs tt;
void jump1(int &x,int ed)
{
if(ed==-) ed=r[x];
while(x!=ed)
{
tt.set(dd[x]);
x=anc[x][];
}
tt.set(dd[x]);
}
void jump2(int &x,int ed)
{
int i,x1=nn[x];
if(!x1) return;
//while(x1!=1&&dep[r[x1]]>=dep[ed]) x1=r[x1];
for(i=TTT::l2n;i>=;i--)
if(dnn1[anr[x1][i]]>=dep[ed])
x1=anr[x1][i];
x1=nn1[x1];
tt|=vvv[vv[nn[x]][nn[x1]]];
x=x1;
}
int t1[];
map<int,int> ma;
int main()
{
//freopen("/tmp/2589/3.in","r",stdin);
//freopen("/tmp/2589/3.ans","w",stdout);
fread(B,,<<,stdin);
init();
int i,a,b,lans=,l;
read(n);read(m);
for(i=;i<=n;i++) read(dd[i]),t1[++t1[]]=dd[i];
sort(t1+,t1+t1[]+);t1[]=unique(t1+,t1+t1[]+)-t1-;
for(i=;i<=t1[];i++) ma[t1[i]]=i;
for(i=;i<=n;i++) dd[i]=ma[dd[i]];
for(i=;i<n;i++)
{
read(a);read(b);
e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
}
GBLOCK::work();LCA::dfs(,);PRE::work();
for(i=;i<=n;i++) r[i]=rt[bl[i]];
TTT::work();
while(m--)
{
tt.reset();
read(a);read(b);
a^=lans;
l=lca(a,b);
if(dep[r[a]]>=dep[l]) jump1(a,-);
if(dep[r[b]]>=dep[l]) jump1(b,-);
jump2(a,l);
jump2(b,l);
jump1(a,l);jump1(b,l);
lans=tt.count();
printf("%d\n",lans);
}
return ;
}
https://www.lydsy.com/JudgeOnline/problem.php?id=4812
此题也是一样的做法，得到一个bitset，之后统计答案
统计答案的话，对于bitset内每一个数字，拆成一些0~0xffff之间的数处理（因为这样就可以预处理了）
统计答案具体方法不写了。。。
注意：如果直接上面那个改改，是过不去的...常数太大
有效卡常：
1.把预处理任意两个关键点之间信息改为只预处理每个关键点到它祖先中所有关键点的信息
2.vector改邻接表
#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef pair<int,int> pii;
char B[<<],*SSS=B;
#define getchar() (*SSS++)
int n,m;
struct E
{
int to,nxt;
}e[];
int f1[],ne;
int dd[];
const int bsz=;
ul lft[];
ul pw[][];
int low[],high[];ul an[][];
template<typename T>
inline void read(T &x)
{
x=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
x*=f;
}
void init()
{
int j,nt,k;
lft[]=;
for(int i=;i<;i++) lft[i]=lft[i-]<<;
for(ul i=;i<=;i++)
{
pw[i][]=;
for(j=;j<=;j++) pw[i][j]=pw[i][j-]*i;
}
for(ul i=,t;i<;i++)
{
nt=;
t=i;
for(j=;j<;j++)
{
if(i&lft[j]) low[i]++,t^=lft[j];
else break;
}
for(j=;j>=;j--)
{
if(i&lft[j]) high[i]++,t^=lft[j];
else break;
}
if(i!=)
{
for(j=;j<;j++)
{
if(t&lft[j]) nt++;
else
{
for(k=;k<=;k++)
{
an[i][k]+=pw[nt][k];
}
nt=;
}
}
for(k=;k<=;k++)
{
an[i][k]+=pw[nt][k];
}
nt=;
}
}
}
struct bs
{
ul d[bsz];
void reset()
{
memset(d,,sizeof(d));
}
void set(int p,bool q=)
{
if(q) d[p>>]|=lft[p&];
else d[p>>]&=~lft[p&];
}
bs &operator|=(const bs &b)
{
for(int i=;i<bsz;i++) d[i]|=b.d[i];
return *this;
}
ul calc(int k)
{
ul ans=,l=;ul t;
#define CAL(t) \
{\
if(t==0xffff) l+=;\
else\
{\
l+=low[t];ans+=pw[l][k];\
ans+=an[t][k];\
l=high[t];\
}\
}
for(int i=;i<bsz;i++)
{
t=d[i]&0xffff;CAL(t);
t=(d[i]>>);CAL(t);
}
return ans+=pw[l][k];
}
};
int bl[],rt[],cnt;
const int sz=;
namespace GBLOCK
{
int st[],tp;
void dfs(int u,int fa)
{
int k,ltp=tp;
for(k=f1[u];k;k=e[k].nxt)
if(e[k].to!=fa)
{
dfs(e[k].to,u);
if(tp-ltp>=sz)
{
rt[++cnt]=u;
while(tp!=ltp) bl[st[tp--]]=cnt;
}
}
st[++tp]=u;
}
void work()
{
dfs(,);
++cnt;rt[cnt]=;
while(tp) bl[st[tp--]]=cnt;
}
}
namespace LCA
{
int anc[][],dep[],l2n=;
void dfs(int u,int fa)
{
int k;
anc[u][]=fa;
dep[u]=dep[fa]+;
for(k=;k<=l2n;k++)
anc[u][k]=anc[anc[u][k-]][k-];
for(k=f1[u];k;k=e[k].nxt)
if(e[k].to!=fa)
dfs(e[k].to,u);
}
int lca(int x,int y)
{
int t,i;
if(dep[x]<dep[y]){t=x;x=y;y=t;}
for(t=dep[x]-dep[y],i=;t>;t>>=,i++)
if(t&) x=anc[x][i];
if(x==y) return x;
for(i=l2n;i>=;i--)
if(anc[x][i]!=anc[y][i])
{
x=anc[x][i];
y=anc[y][i];
}
return anc[x][];
}
}
using LCA::lca;
using LCA::dep;
using LCA::anc;
int nn[],nnn;
bs vv[][];//vv[i][j]:rt[i],rt[j]间答案
int num[];bs vis;
namespace PRE
{
void work()
{
int i,j;
for(i=;i<=cnt;i++)
if(!nn[rt[i]])
nn[rt[i]]=++nnn;
for(i=;i<=n;i++)
if(nn[i])
{
vis.reset();
j=i;vis.set(dd[j]);
vv[nn[i]][nn[i]]=vis;
while(j!=)
{
j=anc[j][];
vis.set(dd[j]);
if(nn[j]) vv[nn[i]][nn[j]]=vis;
}
}
}
}
bs tt;
void jump1(int &x,int ed)
{
if(ed==-) ed=rt[bl[x]];
while(x!=ed)
{
tt.set(dd[x]);
x=anc[x][];
}
tt.set(dd[x]);
}
void jump2(int &x,int ed)
{
int x1=x;
while(x1!=&&dep[rt[bl[x1]]]>=dep[ed]) x1=rt[bl[x1]];
tt|=vv[nn[x]][nn[x1]];
x=x1;
}
int main()
{
//freopen("/tmp/4812/1.in","r",stdin);
//freopen("/tmp/4812/1.ans","w",stdout);
fread(B,,<<,stdin);
init();
int i,a,b,t,l;ul a1,b1;ul lans=;
read(n);read(m);
for(i=;i<=n;i++) read(dd[i]);
for(i=;i<n;i++)
{
read(a);read(b);
e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
}
GBLOCK::work();LCA::dfs(,);PRE::work();
while(m--)
{
read(t);tt.reset();
for(i=;i<=t;i++)
{
read(a1);read(b1);
a=a1^lans;b=b1^lans;
l=lca(a,b);
if(a!=&&dep[rt[bl[a]]]>=dep[l]) jump1(a,-);
if(b!=&&dep[rt[bl[b]]]>=dep[l]) jump1(b,-);
jump2(a,l);
jump2(b,l);
jump1(a,l);jump1(b,l);
}
read(t);
lans=tt.calc(t);
printf("%u\n",lans);
}
return ;
}