QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196173 | #5372. 杀蚂蚁简单版 | by_chance | 0 | 0ms | 0kb | C++14 | 3.6kb | 2023-10-01 13:46:03 | 2023-10-01 13:46:03 |
Judging History
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%