树与异或

C++14(g++5.4) 解法, 执行用时: 2104ms, 内存消耗: 25984K, 提交时间: 2020-04-18 18:40:35

#include<bits/stdc++.h>
#define M 100002
using namespace std;
char c;
int Read(){
	while(!isdigit(c=getchar()));
	int res=c^48;
	while(isdigit(c=getchar()))res=(res<<3)+(res<<1)+(c^48);
	return res;
}
int n,f[M],A[M],dep[M],stk[M],Ans[M],dfn[M],R[M],id1[M],id2[M],tp[M],Big[M],sz[M],S,tot,cnt,top;
int mark[M],ans,mem[M];
vector<int>son[M],W[M],U[M];
struct ll{
	int u,v,z,ID;
}Q[M];
bool cmp(ll a,ll b){
	if(id1[a.u]!=id1[b.u])return id1[a.u]<id1[b.u];
	return dfn[a.v]<dfn[b.v];
}
void dfs(int x,int fa){
	int l=top;
	dfn[x]=++tot,dep[x]=dep[fa]+1,f[x]=fa,sz[x]=1,Big[x]=0;
	for(int i=0;i<son[x].size();++i){
		int y=son[x][i];
		if(y==fa)continue;
		dfs(y,x);
		sz[x]+=sz[y];
		if(sz[y]>sz[Big[x]])Big[x]=y;
		if(top-l>=S){
			++cnt;
			while(top>l)id1[stk[top--]]=cnt;
		}
	}
	R[x]=tot;
	stk[++top]=x;
}
void redfs(int x,int t){
	tp[x]=t;
	if(Big[x])redfs(Big[x],t);
	for(int i=0;i<son[x].size();++i){
		int y=son[x][i];
		if(y==f[x]||y==Big[x])continue;
		redfs(y,y);
	}
}
int LCA(int a,int b){
	while(tp[a]!=tp[b]){
		if(dep[tp[a]]<dep[tp[b]])swap(a,b);
		a=f[tp[a]];
	}
	return dep[a]<dep[b]?a:b;
}
void Go(int u,int v){
	while(u!=v){
		if(dep[u]<dep[v])swap(u,v);
		if(mem[u])mem[u]=0,mark[A[u]]--,ans-=(mark[A[u]]==0);
		else mem[u]=1,mark[A[u]]++,ans+=(mark[A[u]]==1);
		u=f[u];
	}
}
int C[M];
void update(int x,int num){
	while(x<=n){
		C[x]+=num;
		x+=x&-x;
	}
}
int query(int x){
	int res=0;
	while(x){
		res+=C[x];
		x-=x&-x;
	}
	return res;
}
int main(){
	int T=Read(),ca=0,mx;
	while(T--){
		tot=cnt=ans=mx=0;
		n=Read(),S=sqrt(n);
		for(int i=1;i<=n;++i)mx=max(mx,A[i]=Read()),U[A[i]].push_back(i);
		for(int i=1,u,v;i<n;++i){
			u=Read(),v=Read();
			son[u].push_back(v),son[v].push_back(u);
		}
		dfs(1,0),redfs(1,1);
		++cnt;
		while(top)id1[stk[top--]]=cnt;
		for(int i=1;i<=n;++i)id2[i]=i/S;
		int q=Read();
		for(int i=1;i<=q;++i)Q[i].u=Read(),Q[i].v=Read(),Q[i].z=Read(),Q[i].ID=i;
		sort(Q+1,Q+q+1,cmp);
		memset(mem,0,sizeof(mem));
		memset(mark,0,sizeof(mark));
		for(int i=1;i<=q;++i){
			Go(Q[i-1].u,Q[i].u),Go(Q[i-1].v,Q[i].v);
			W[Q[i].z].push_back(i);
			Ans[Q[i].ID]=ans;
			if(mark[A[LCA(Q[i].u,Q[i].v)]]==0)Ans[Q[i].ID]++;
		}
		for(int i=1;i<=mx;++i){
			if(!W[i].size())continue;
			for(int j=i;j<=mx;j+=i){
				for(int k=0;k<U[j].size();++k){
					int y=U[j][k];
					update(dfn[y],1);
					update(R[y]+1,-1);
				}
			}
			for(int j=0;j<W[i].size();++j){
				int y=W[i][j];
				int lca=LCA(Q[y].u,Q[y].v);
				Ans[Q[y].ID]^=(query(dfn[Q[y].u])+query(dfn[Q[y].v])-2*query(dfn[lca])+(A[lca]%i==0));
			}
			for(int j=i;j<=mx;j+=i){
				for(int k=0;k<U[j].size();++k){
					int y=U[j][k];
					update(dfn[y],-1);
					update(R[y]+1,1);
				}
			}
		}
		printf("Case #%d:\n",++ca);
		for(int i=1;i<=q;++i)printf("%d\n",Ans[i]);
		for(int i=1;i<=M-2;++i)son[i].clear(),W[i].clear(),U[i].clear();
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1240ms, 内存消耗: 41428K, 提交时间: 2020-04-18 08:37:13

#include<bits/stdc++.h>
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

#define pb push_back

char IO;
template<class T=int> T rd(){
	T s=0;
	int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e5+10;

int n,m,len,a[N];
vector <int> G[N],Fac[N];
struct Que{ int x,k,id; };
vector <Que> Q[N];
struct Node{ int l,r,lca,id; } A[N];
int ans[N],dep[N],fa[N][20];
int line[N<<1],L[N],R[N],dfn;

void pre_dfs(int u,int f) {
	line[L[u]=++dfn]=u,fa[u][0]=f;
	rep(i,1,17) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int v:G[u]) if(v!=f) dep[v]=dep[u]+1,pre_dfs(v,u);
	line[R[u]=++dfn]=u;
}
int LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=0,del=dep[x]-dep[y];(1<<i)<=del;++i) if(del&(1<<i)) x=fa[x][i];
	if(x==y) return x;
	drep(i,17,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

int vis[N],cnt[N],Now;
void Add(int x){ if((cnt[x]++)==0) Now++; }
void Del(int x){ if((--cnt[x])==0) Now--; }
void Upd(int x){ vis[x]?Del(a[x]):Add(a[x]),vis[x]^=1; }

void dfs(int u,int f) {
	for(int t:Fac[a[u]]) cnt[t]++;
	for(Que t:Q[u]) ans[t.id]+=cnt[t.x]*t.k;
	for(int v:G[u]) if(v!=f) dfs(v,u);
	for(int t:Fac[a[u]]) cnt[t]--;
}

int main(){
	rep(i,1,N-1) for(int j=i;j<N;j+=i) Fac[j].pb(i);
	rep(kase,1,rd()) {
		n=rd();
		rep(i,1,n) G[i].clear(),Q[i].clear(),vis[i]=0;
		rep(i,1,n) a[i]=rd();
		rep(i,2,n) {
			int u=rd(),v=rd();
			G[u].pb(v),G[v].pb(u);
		}
		dfn=0,pre_dfs(1,0);
		len=sqrt(n*2);
		rep(i,1,m=rd()) {
			int x=rd(),y=rd(),z=rd(),lca=LCA(x,y);
			if(L[x]>L[y]) swap(x,y);
			if(lca==x) A[i]=(Node){L[x],L[y],0,i};
			else A[i]=(Node){R[x],L[y],lca,i};
			Q[x].pb((Que){z,1,i}),Q[y].pb((Que){z,1,i});
			Q[lca].pb((Que){z,-1,i}),Q[fa[lca][0]].pb((Que){z,-1,i});
		}
		rep(i,1,m) ans[i]=0;
		dfs(1,0);
		sort(A+1,A+m+1,[&](Node x,Node y){ return x.l/len<y.l/len||(x.l/len==y.l/len && x.r<y.r);});
		int l=1,r=0;
		rep(i,1,m) {
			while(l<A[i].l) Upd(line[l++]);
			while(l>A[i].l) Upd(line[--l]);
			while(r>A[i].r) Upd(line[r--]);
			while(r<A[i].r) Upd(line[++r]);
			if(A[i].lca) Upd(A[i].lca);
			ans[A[i].id]^=Now;
			if(A[i].lca) Upd(A[i].lca);
		}
		rep(i,1,n) cnt[a[i]]=0;
		Now=0;
		printf("Case #%d:\n",kase);
		rep(i,1,m) printf("%d\n",ans[i]);
	}
}

详情