QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196173#5372. 杀蚂蚁简单版by_chance0 0ms0kbC++143.6kb2023-10-01 13:46:032023-10-01 13:46:03

Judging History

This is the latest submission verdict.

  • [2023-10-01 13:46:03]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2023-10-01 13:46:03]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
bool mem1;
typedef unsigned long long ull;
const int N=1e5+5,P=998244353;
struct Matrix{
	ull a[3][3];
	Matrix(){
		a[0][0]=a[0][1]=a[0][2]=
		a[1][0]=a[1][1]=a[1][2]=
		a[2][0]=a[2][1]=a[2][2]=0;
	}
	Matrix operator *(const Matrix&b)const{
		Matrix c;
		c.a[0][0]=(a[0][0]*b.a[0][0]+a[0][1]*b.a[1][0]+a[0][2]*b.a[2][0])%P;
		c.a[0][1]=(a[0][0]*b.a[0][1]+a[0][1]*b.a[1][1]+a[0][2]*b.a[2][1])%P;
		c.a[0][2]=(a[0][0]*b.a[0][2]+a[0][1]*b.a[1][2]+a[0][2]*b.a[2][2])%P;
		c.a[1][0]=(a[1][0]*b.a[0][0]+a[1][1]*b.a[1][0]+a[1][2]*b.a[2][0])%P;
		c.a[1][1]=(a[1][0]*b.a[0][1]+a[1][1]*b.a[1][1]+a[1][2]*b.a[2][1])%P;
		c.a[1][2]=(a[1][0]*b.a[0][2]+a[1][1]*b.a[1][2]+a[1][2]*b.a[2][2])%P;
		c.a[2][0]=(a[2][0]*b.a[0][0]+a[2][1]*b.a[1][0]+a[2][2]*b.a[2][0])%P;
		c.a[2][1]=(a[2][0]*b.a[0][1]+a[2][1]*b.a[1][1]+a[2][2]*b.a[2][1])%P;
		c.a[2][2]=(a[2][0]*b.a[0][2]+a[2][1]*b.a[1][2]+a[2][2]*b.a[2][2])%P;
		return c;
	}
}g[N][20],zero;
ull qpow(ull a,ull b=P-2){
	ull c=1;
	for(;b;b>>=1,a=1ll*a*a%P)
		if(b&1)c=c*a%P;
	return c;
}
int n,q,fa[N][20],dep[N],L[N],R[N],dcnt;
ull a[N],s[N],f[N],val[N],pd[N][20];
vector<int> G[N];
void dfs(int u){
	L[u]=++dcnt;
	val[u]=s[u]*qpow(a[fa[u][0]])%P;
	if(u>2){
		int v=fa[u][0],w=fa[v][0];
		g[u][0].a[0][0]=a[u]*qpow(a[w])%P;
		g[u][0].a[1][0]=s[v]*qpow(a[w])%P;
		g[u][0].a[0][2]=g[u][0].a[1][1]=g[u][0].a[2][2]=1;
		f[u]=a[w]*f[v]%P*qpow(a[w]*f[v]%P+a[u])%P;
		pd[u][0]=P+1-f[u];
	}
	for(int v:G[u])if(fa[u][0]!=v)
		fa[v][0]=u,dep[v]=dep[u]+1,dfs(v);
	R[u]=dcnt;
}
void pre(){
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n;i++)if(fa[i][j-1])
			fa[i][j]=fa[fa[i][j-1]][j-1],
			g[i][j]=g[i][j-1]*g[fa[i][j-1]][j-1],
			pd[i][j]=pd[i][j-1]*pd[fa[i][j-1]][j-1]%P;
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);int d=dep[u]-dep[v];
	for(int i=17;i>=0;--i)if(d&(1<<i))u=fa[u][i];
	if(u==v)return u;
	for(int i=17;i>=0;--i)
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int find(int u,int d){
	d=dep[u]-d;if(d<0)return 0;
	for(int i=17;i>=0;--i)
		if(d&(1<<i))u=fa[u][i];
	return u;
}
void calc(int u,int d,Matrix&res){
	d=dep[u]-d;if(d<0){res=zero;return;}
	for(int i=17;i>=0;--i)
		if(d&(1<<i))res=res*g[u][i],u=fa[u][i];
}
ull calc2(int u,int d){
	d=dep[u]-d;ull res=1;
	for(int i=17;i>=0;--i)
		if(d&(1<<i))res=res*pd[u][i]%P,u=fa[u][i];
	return res;
} 
bool mem2;
int main(){
	cerr<<(&mem1-&mem2)/1024/1024<<endl;
	freopen("ant3.in","r",stdin);
	freopen("ant.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%llu",a+i);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);s[u]+=a[v];
		G[v].push_back(u);s[v]+=a[u];
	}
	f[2]=1;dfs(1);pre();
	for(int i=2;i<=n;i++)
		f[i]=f[i]*a[fa[i][0]]%P*qpow(s[i])%P;
	scanf("%d",&q);
	for(int i=1,st,u,v;i<=q;i++){
		scanf("%d%d%d",&st,&u,&v);
		int w=LCA(u,v);ull ans=0,mul=1;
		if(!(L[st]>=L[w]&&L[st]<=R[w]))
			st=LCA(st,w),mul=calc2(w,dep[st]),st=w;
		if(LCA(v,st)!=w)swap(u,v);
		Matrix c;st=LCA(u,st);
		c.a[0][0]=val[u];c.a[0][1]=1;c.a[0][2]=0;
		calc(u,dep[st],c);ans=(ans+P-c.a[0][2])%P;
		c=zero;c.a[0][0]=val[u];c.a[0][1]=1;c.a[0][2]=0;
		calc(u,dep[w],c);ans=(ans+c.a[0][2])%P;
		c=zero;c.a[0][0]=val[u];c.a[0][1]=1;c.a[0][2]=0;
		calc(u,dep[w]+1,c);ull gu=c.a[0][0];
		c=zero;c.a[0][0]=val[v];c.a[0][1]=1;c.a[0][2]=0;
		calc(v,dep[w]+1,c);ull gv=c.a[0][0];
		int x=find(u,dep[w]+1),y=find(v,dep[w]+1);
		ull tmp=1;
		if(x)tmp=(tmp+gu*a[x]%P*qpow(s[w])%P)%P;
		if(y)tmp=(tmp+gv*a[y]%P*qpow(s[w])%P)%P;
		ans=(ans+tmp*qpow(f[w])%P)%P;
		printf("%llu\n",ans*mul%P);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

5
1 1 1 1 1
1 2
2 3
2 4
3 5
1
2 4 2

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Dangerous Syscalls

Test #18:

score: 0
Dangerous Syscalls

input:

100000
13643 13546 7538 2233 7731 14619 19601 8438 9556 19888 17313 1060 15168 11207 11183 16074 10758 7469 13444 9658 18326 4735 7542 13836 5863 7903 7212 14714 10416 18506 13435 14502 15271 13205 14887 18074 8353 19807 1767 19148 7343 10823 14211 66 17168 8305 1210 5436 18552 3659 886 18416 19261 ...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%