孙江淏

BALENCIAGA  •  3个月前


include

include

include

include

include

include

include

include

include

using namespace std;

define MAXN 500005

typedef long long LL; const LL mo=998244353; template void read(_T &x){

_T f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;

} void add(LL &x,LL y){x+=y;if(x>=mo)x-=mo;} int n,m,head[MAXN],dep[MAXN],tot,cnt,root[MAXN]; vectorG[MAXN]; struct ming{int lson,rson;LL sum,mul;}tr[MAXN<<5]; struct edge{int to,nxt;}e[MAXN<<1]; void addEdge(int u,int v){e[++tot]=(edge){v,head[u]};head[u]=tot;} void pushdown(int rt){ if(tr[rt].lson){ tr[tr[rt].lson].sum=tr[tr[rt].lson].sumtr[rt].mul%mo; tr[tr[rt].lson].mul=tr[tr[rt].lson].multr[rt].mul%mo; } if(tr[rt].rson){ tr[tr[rt].rson].sum=tr[tr[rt].rson].sumtr[rt].mul%mo; tr[tr[rt].rson].mul=tr[tr[rt].rson].multr[rt].mul%mo; } tr[rt].mul=1; } void modify(int &rt,int l,int r,int ai){ if(!rt)rt=++cnt;tr[rt].sum=tr[rt].mul=1; if(l==r)return ;int mid=l+r>>1;

if(ai<=mid)modify(tr[rt].lson,l,mid,ai);
else modify(tr[rt].rson,mid+1,r,ai);

} LL query(int rt,int l,int r,int al){

if(!rt||r<=al)return tr[rt].sum;
int mid=l+r>>1;LL res=0;pushdown(rt);
if(mid<al)add(res,query(tr[rt].rson,mid+1,r,al));
add(res,query(tr[rt].lson,l,mid,al));
return res;

} int merge(int x,int y,int l,int r,LL &s1,LL &s2){

if(!x&&!y)return 0;
if(!x||!y){
	add(x?s2:s1,tr[x+y].sum);
	tr[x+y].mul=tr[x+y].mul*(x?s1:s2)%mo;
	tr[x+y].sum=tr[x+y].sum*(x?s1:s2)%mo;
	return x+y;
}
if(l==r){
	LL tx=tr[x].sum,ty=tr[y].sum;add(s1,ty);
	tr[x].sum=(tr[x].sum*s1%mo+tr[y].sum*s2%mo)%mo;
	add(s2,tx);return x;
}
pushdown(x);pushdown(y);int mid=l+r>>1;
tr[x].lson=merge(tr[x].lson,tr[y].lson,l,mid,s1,s2);
tr[x].rson=merge(tr[x].rson,tr[y].rson,mid+1,r,s1,s2);
tr[x].sum=(tr[tr[x].lson].sum+tr[tr[x].rson].sum)%mo;
return x;

} void dfs(int u,int fa){

dep[u]=dep[fa]+1;int mxd=0,siz=G[u].size();
for(int i=0;i<siz;i++)mxd=max(mxd,dep[G[u][i]]);
modify(root[u],0,n,mxd);
for(int i=head[u];i;i=e[i].nxt){
	int v=e[i].to;if(v==fa)continue;
	dfs(v,u);LL tmp=query(root[v],0,n,dep[u]),sm=0;
	root[u]=merge(root[u],root[v],0,n,tmp,sm);
}

} signed main(){

read(n);
for(int i=1;i<n;i++){
	int u,v;read(u);read(v);
	addEdge(u,v);addEdge(v,u);
}
read(m);
for(int i=1;i<=m;i++){
	int u,v;read(u);read(v);
	G[v].push_back(u);
}
dfs(1,0);printf("%lld\n",query(root[1],0,n,0));
return 0;

}


评论:

666


刘文捷(真的)  •  3个月前

请先登录,才能进行评论