F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 4812 >> 求助!树剖RE了,但看不出来哪里有问题...
2017gdgzoi115 @ 2020-01-19 10:46:05
[ Quote ] [ Edit ] [ Delete ] 1#
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100010,W=30000,bl=1e3;
const long long mod=4294967296;
bitset<W+100>f[110][110];
bitset<W+100>cur;
ll n,m,cnt=0,tot=0;
ll w[N];
ll to[N<<1],nxt[N<<1],head[N];
ll siz[N],d[N],son[N],father[N],tp[N],dfn[N],a[N];
ll block[N],l[N],r[N];

void add(ll u,ll v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}

void dfs1(ll u,ll fa)
{
// cout<<"u="<<u<<endl;
siz[u]=1;
son[u]=0;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
// cout<<"v="<<v<<endl;
if(v==fa)continue;
d[v]=d[u]+1;
father[v]=u;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}

void dfs2(ll u,ll topp)
{
dfn[u]=++tot;
a[tot]=w[u];
tp[u]=topp;
if(son[u])dfs2(son[u],topp);
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==father[u]||v==son[u])continue;
dfs2(v,v);
}
}

void pre()
{
for(ll i=1;i<=n;i++)
{
block[i]=(i-1)/bl+1;
f[block[i]][block[i]].set(a[i]);
}
for(ll i=1;i<=block[n];i++)
{
for(ll j=i+1;j<=block[n];j++)
{
f[i][j]=f[i][j-1]|f[j][j];
}
}
for(ll i=1;i<=block[n];i++)l[i]=r[i-1]+1,r[i]=i*bl;
}

void workblock(long long L,long long R)
{
if(block[L]==block[R])
{
for(ll i=L;i<=R;i++)cur.set(a[i]);
return ;
}
cur|=f[block[L]+1][block[R]-1];
for(ll i=L;i<=r[block[L]];i++)cur.set(a[i]);
for(ll i=l[block[R]];i<=R;i++)cur.set(a[i]);
}

void worktree(long long x,long long y)
{
while(tp[x]!=tp[y])
{
if(d[tp[x]]<d[tp[y]])swap(x,y);
workblock(dfn[tp[x]],dfn[x]);
x=father[tp[x]];
}
if(dfn[x]>dfn[y])swap(x,y);
workblock(dfn[x],dfn[y]);
}

ll k;

long long poww(long long x,ll b)
{
long long res=1ll,tmp=x;
while(b)
{
if(b&1)res=(res*tmp)%mod;
b>>=1;
tmp=(tmp*tmp)%mod;
}
return res%mod;
}

long long query()
{
long long num=0ll,ans=0ll;
for(ll i=0;i<=W;i++)
{
if(cur.test(i))num++;
else
{
if(num)ans=(ans+poww(num,k))%mod;
num=0;
}
}
return ans;
}

int main()
{
// freopen("1.in","r",stdin);
// freopen("output.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(ll i=1;i<=n;i++)scanf("%lld",&w[i]);
ll x,y,t;
for(ll i=1;i<n;i++)
{
scanf("%lld %lld",&x,&y);
add(x,y),add(y,x);
}
d[1]=1;
dfs1(1,0);
dfs2(1,1);
pre();
long long lastans=0ll;
long long xx,yy;
for(ll i=1;i<=m;i++)
{
scanf("%lld",&t);
cur.reset();
for(ll j=1;j<=t;j++)
{
scanf("%lld %lld",&xx,&yy);
xx=xx^lastans,yy=yy^lastans;
worktree(xx,yy);
}
scanf("%lld",&k);
printf("%lld\n",lastans=query());
}
return 0;
}
/*
8 2
1 9 2 6 0 8 1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2 1 4 5 8 3
1 90 90 2
*/
[Top] [Previous Page] [Next Page]

HOME Back