萌新求助
- 板块P6177 Count on a tree II/【模板】树分块
- 楼主clamee
- 当前回复1
- 已保存回复1
- 发布时间2020/9/10 19:54
- 上次更新2023/11/5 13:27:51
查看原帖
被骇客银狼阻止的越权访问保存失败
萌新求助
写了300多行，调不动了。有大佬帮忙调一下吗？
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
il int read()
{
int re=0,k=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
return re*k;
}
il void write(int x)
{
if(x<0)return putchar('-'),write(-x),void();
if(x<10)return putchar(x+48),void();
return write(x/10),write(x%10),void();
}
const int BB=201;
int h[100005],l[100005],head[100005],tot,d[100005],fa[100005],top[100005],n,a[100005],sz[100005],son[100005],f[205][100005],p[205],ls,t[100005],c[100005],g[100005];
int fs[200005],tt;
bool vis[100005];
int vis2[100005],vis1[100005];
struct ss{
int node,nxt;
}e[100005];
void add(int u,int v)
{
e[++tot].nxt=head[u];
e[tot].node=v;
head[u]=tot;
}
void dfs(int x,int ffa,int dp)
{
fa[x]=ffa;
d[x]=dp;
sz[x]=1;
int maxsz=-1;
for(int i=head[x];i;i=e[i].nxt)
{
int k=e[i].node;
if(k==ffa)continue;
if(!vis[k])
g[k]=g[x];
else g[k]=k;
dfs(k,x,dp+1);
sz[x]+=sz[k];
if(maxsz<sz[k])maxsz=sz[k],son[x]=k;
}
}
void ddfs(int x,int tt)
{
//id[x]=++cnt;
//ans[cnt]=w[x];
top[x]=tt;
if(!son[x])return;
ddfs(son[x],tt);
l[a[x]]=h[a[x]];
h[a[x]]=x;
for(int i=head[x];i;i=e[i].nxt)
{
int k=e[i].node;
if(fa[x]==k||son[x]==k)continue;
ddfs(k,k);
}
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
//cerr<<x<<" "<<top[x]<<" "<<y<<" "<<top[y]<<endl;
if(d[top[x]]<d[top[y]])swap(x,y);
x=fa[top[x]];
}
if(d[x]>d[y])swap(x,y);
return x;
}
void dp(int x,int fa,int *ff,int *s,int ls,int ans)
{
//cerr<<x<<" "<<tt<<endl;
if(!x)return;
s[++ls]=a[x];
//int p=vis2[a[x]];
if(t[a[x]]&&!vis2[a[x]])ans++;
vis2[s[ls]]++;
if(vis[x])
{
for(int i=1;i<=ls;i++)
{
if(!t[s[i]])tt++;
t[s[i]]++,vis2[s[i]]--;
}
ff[x]=tt;
}
else ff[x]=ans;
//swap(vis2[a[x]],p);
//cerr<<x<<endl;
for(rg int i=head[x];i;i=e[i].nxt)
{
if(e[i].node==fa)continue;
if(vis[x])
{
dp(e[i].node,x,ff,s+ls,0,0);
}
else
{
dp(e[i].node,x,ff,s,ls,ans);
}
}
//vis2[a[x]]=p;
if(vis[x])
{
for(int i=1;i<=ls;i++)
{
t[s[i]]--;vis2[s[i]]++;
//cerr<<t[s[i]]<<endl;
if(!t[s[i]])tt--/*,cerr<<1*/;
}
}
vis2[s[ls]]--;
ls--;
//vis2[a[x]]=p;
}
int b[100005],cnt,q;
int main()
{
freopen("2.in","r",stdin);
freopen("2.out","w",stdout);
n=read();q=read();
for(rg int i=1;i<=n;i++)
{
b[++cnt]=a[i]=read();
c[i]=i;
}
for(rg int i=1,u,v;i<n;i++)
{
u=read();v=read();
add(u,v);add(v,u);
}
srand(time(0));
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
random_shuffle(c+2,c+n+1);
for(rg int i=1;i<=n;i++)
{
if(i<=BB)p[i]=c[i],vis[c[i]]=1;
a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
// if(i<=B)cerr<<p[i]<<endl;
}
//cerr<<"read over"<<endl;
g[1]=1;
dfs(1,0,1);
ddfs(1,1);
//cerr<<1;
for(rg int i=1;i<=BB;i++)
{
dp(p[i],0,f[i],fs,0,0);
memset(vis2,0,sizeof(vis2));
memset(t,0,sizeof(t));//tt=0;
}
int lans=0;
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
for(rg int i=1,u,v;i<=q;i++)
{
// cerr<<i<<endl;
u=read()^lans;v=read();
if(g[u]==g[v])
{
//cerr<<1<<endl;
lans=0;
int x=u,y=v,LCA=lca(u,v);
while(x!=LCA){if(!vis1[a[x]])lans++;vis1[a[x]]=1;x=fa[x];}
while(y!=LCA){if(!vis1[a[y]])lans++;vis1[a[y]]=1;y=fa[y];}
if(!vis1[a[LCA]])lans++;
while(u!=LCA){vis1[a[u]]=0;u=fa[u];}
while(v!=LCA){vis1[a[v]]=0;v=fa[v];}
write(lans);puts("");continue;
}
int LCA=lca(u,v);
// cerr<<d[g[u]]<<" "<<d[LCA]<<" "<<d[g[v]]<<endl;
if(d[g[u]]<d[LCA]||d[g[v]]<d[LCA])
{
//cerr<<2<<endl;
if(d[g[u]]<d[LCA])swap(u,v);
int x=u,y=v,z=u,A=0,B=0,C=0,AB=0,BC=0,AC=0,ABC=0,xx=u,yy=v,ty;
while(!vis[x]&&x!=LCA){if(!vis1[a[x]])A++;vis1[a[x]]=x;x=fa[x];}
while(!vis[y]&&y!=LCA)
{
if(!vis2[a[y]])
{
B++;
if(vis1[a[y]])
{
AB++;
}
}
vis2[a[y]]=y;y=fa[y];
}
while(d[g[fa[g[z]]]]>d[LCA])z=fa[g[z]];
ty=z=g[z];
z=fa[z];
int zz=z;
while(!vis[z]&&z!=LCA)
{
if(!vis2[a[z]])
{
B++;
if(vis1[a[z]])
{
AB++;
}
}
vis2[a[z]]=z;z=fa[z];
}
//cerr<<(y==LCA)<<endl;
if(!vis2[a[LCA]])
{
B++;
if(vis1[a[LCA]])AB++;
}
vis2[a[LCA]]=LCA;
// cerr<<2<<endl;
while(!vis[yy]&&yy!=LCA)
{
if(vis2[a[yy]]&&vis1[a[yy]])
{
if((d[l[vis1[a[yy]]]]>=d[ty]&&d[l[vis1[a[yy]]]]<=d[x]))
ABC++;
}
vis2[a[yy]]=0;yy=fa[yy];
// cerr<<yy<<endl;
}
// cerr<<2<<endl;
while(!vis[zz]&&zz!=LCA)
{
if(vis2[a[zz]]&&vis1[a[zz]])
{
if((d[l[vis1[a[zz]]]]>=d[ty]&&d[l[vis1[a[zz]]]]<=d[x]))
ABC++;
}
vis2[a[zz]]=0;zz=fa[zz];
}
if(vis2[a[LCA]])
{
if(vis1[a[LCA]])
if((d[l[vis1[a[LCA]]]]>=d[ty]&&d[l[vis1[a[LCA]]]]<=d[x]))
ABC++;
}
vis2[a[LCA]]=0;
// cerr<<2<<endl;
while(!vis[xx]&&xx!=LCA){vis1[a[xx]]=0;xx=fa[xx];}
for(rg int j=1;j<=BB;j++)
if(p[j]==x){x=j;break;}
for(rg int j=1;j<=BB;j++)
if(p[j]==ty){ty=j;break;}
C=f[x][p[ty]];
//if(i==3)cerr<<vis[u]<<" "<<vis[v]<<endl;
//cerr<<i<<endl;
if(!vis[v])AC=f[x][v];
if(!vis[u])BC=f[ty][u];
lans=A+B+C-AB-BC-AC+ABC;
write(lans);puts("");continue;
}
//cerr<<3<<endl;
int x=u,y=v,A=0,B=0,C=0,AB=0,BC=0,AC=0,ABC=0,xx=u,yy=v;
while(!vis[x]&&x!=LCA){if(!vis1[a[x]])A++;vis1[a[x]]=x;x=fa[x];}
while(!vis[y]&&y!=LCA)
{
if(!vis2[a[y]])
{
B++;
if(vis1[a[y]])
{
AB++;
}
}
vis2[a[y]]=y;y=fa[y];
}
// cerr<<3<<endl;
while(!vis[yy]&&yy!=LCA)
{
if(vis2[a[yy]]&&vis1[a[yy]])
{
if((d[l[vis1[a[yy]]]]>=d[LCA]&&d[l[vis1[a[yy]]]]<=d[x])||(d[l[vis2[a[yy]]]]>=d[LCA]&&d[l[vis2[a[yy]]]]<=d[y]))
ABC++;
}
vis2[a[yy]]=0;yy=fa[yy];
}
//cerr<<3<<endl;
while(!vis[xx]&&xx!=LCA){vis1[a[xx]]=0;xx=fa[xx];}
//cerr<<3<<endl;
for(rg int j=1;j<=BB;j++)
if(p[j]==x){x=j;break;}
for(rg int j=1;j<=BB;j++)
if(p[j]==y){y=j;break;}
// cerr<<3<<endl;
C=f[x][p[y]];
// cerr<<LCA<<" "<<d[LCA]<<" "<<d[y]<<" "<<d[g[v]]<<" "<<vis[y]<<" "<<u<<endl;
if(!vis[v])AC=f[x][v];
//cerr<<3<<endl;
if(!vis[u])BC=f[y][u];
// cerr<<3<<endl;
lans=A+B+C-AB-BC-AC+ABC;
write(lans);puts("");
}
}
加载中...