F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 2589 >> 树上分块,拍过了,不知道为什么还是RE?
201610128 @ 2020-03-23 22:00:16
[ Quote ] [ Edit ] [ Delete ] 1#
RT,写了树分块选关键点+自带bitset的做法,不知道为什么RE了?求教!
201610128 @ 2020-03-24 13:37:23
[ Quote ] [ Edit ] [ Delete ] 2#
现在改为TLE了。请问怎么卡常?
201610128 @ 2020-03-24 13:37:29
[ Quote ] [ Edit ] [ Delete ] 3#
#include<cstdio>
#include<cstring>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cmath>
using namespace std;

#define bs bitset<maxn>
const int maxn=40010,lim=500;
int n,m,tot,head[maxn],ans,a[maxn],b[maxn];
int dep[maxn],siz[maxn],son[maxn],tp[maxn],fa[maxn];
int st[maxn/lim+10],pos,f[maxn],md[maxn],tag[maxn];
bs s[maxn/lim+10][maxn/lim+10],cur;
struct node
{
int nxt,to;
}edge[maxn<<1];

const int ml=(1<<21)+10;
char buf[ml],*p1=buf,*p2=buf;

char get_char()
{
return p1==p2&&(p2=(p1=buf)+fread(buf,1,ml,stdin),p1==p2)?EOF:*p1++;
}

int read()
{
register int x=0;
register char c=get_char();
while (c<48||c>57)
c=get_char();
while (c>=48&&c<=57)
x=(x<<1)+(x<<3)+(c^48),c=get_char();
return x;
}

void add(int u,int v)
{
edge[++tot]=(node){head[u],v};
head[u]=tot;
}

void dfs1(int u,int f)
{
dep[u]=dep[f]+1;
fa[u]=f;
dep[u]=md[u]=dep[f]+1;
siz[u]=1;
register int i,v;
for (i=head[u];i;i=edge[i].nxt)
{
v=edge[i].to;
if (v!=f)
{
dfs1(v,u);
siz[u]+=siz[v];
if (siz[v]>siz[son[u]])
son[u]=v;
md[u]=max(md[u],md[v]);
}
}
if (md[u]-dep[u]>=lim)
md[u]=dep[u],tag[u]=++tot;
}

void dfs(int u)
{
register int i,v,p,q,x;
for (i=head[u];i;i=edge[i].nxt)
{
v=edge[i].to;
if (v!=fa[u])
{
if (tag[v])
{
p=tag[st[pos]],q=tag[v];
for (x=v;x!=st[pos];x=fa[x])
s[p][q].set(a[x]);
for (i=1;i<pos;i++)
{
// s[tag[st[i]]][q]=(s[tag[st[i]]][p]|s[p][q]);
// s[tag[st[i]]][q]=s[tag[st[i]]][p];
// s[tag[st[i]]][q]|=s[p][q];
(s[tag[st[i]]][q]|=s[tag[st[i]]][p])|=s[p][q];
}
f[v]=st[pos];
st[++pos]=v;
}
dfs(v);
if (tag[v])
--pos;
}
}
}

void dfs2(int u,int top)
{
tp[u]=top;
register int i;
if (!son[u])
return;
dfs2(son[u],top);
for (i=head[u];i;i=edge[i].nxt)
if (edge[i].to!=fa[u]&&edge[i].to!=son[u])
dfs2(edge[i].to,edge[i].to);
}

inline int lca(int u,int v)
{
while (tp[u]!=tp[v])
{
if (dep[tp[u]]<dep[tp[v]])
v=fa[tp[v]];
else
u=fa[tp[u]];
}
if (dep[u]<dep[v])
return u;
return v;
}

int main()
{
int i,t,u,v;
n=read(),m=read();
for (i=1;i<=n;i++)
a[i]=b[i]=read();
sort(b+1,b+n+1);
tot=unique(b+1,b+n+1)-(b+1);
for (i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
tot=0;
for (i=1;i<=n-1;i++)
{
u=read(),v=read();
add(u,v),add(v,u);
}
tot=0;
dfs1(1,0);
if (!tag[1])
tag[1]=++tot;
st[++pos]=1;
dfs(1);
dfs2(1,1);
while (m--)
{
u=read()^ans,v=read();
t=lca(u,v);
cur.reset();
while (u!=t&&!tag[u])
cur.set(a[u]),u=fa[u];
while (v!=t&&!tag[v])
cur.set(a[v]),v=fa[v];
if (u!=t)
{
i=u;
while (dep[f[i]]>=dep[t])
i=f[i];
if (i!=u)
cur|=s[tag[i]][tag[u]];
while (i!=t)
cur.set(a[i]),i=fa[i];
}
if (v!=t)
{
i=v;
while (dep[f[i]]>=dep[t])
i=f[i];
if (i!=v)
cur|=s[tag[i]][tag[v]];
while (i!=t)
cur.set(a[i]),i=fa[i];
}
cur.set(a[t]);
ans=cur.count();
printf("%d\n",ans);
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back