Description

LOJ3340

$n,m<=5e5$

Solution

首先很容易想到$n^2$的DP，$f[x][j]$表示$x$点的限制到$j$。把有用的状态提出来就可以用$n^2$获得64分。启发式合并可以做到$nlo{g}^{2}n$获得更多分数。很容易就可以在DP的基础上想到线段树合并。但是我考场上的时候想的是前缀和的状态的合并，需要单点乘以及区间加，并且将一段赋为0。由于这个需要维护一个$kx+b$的tag，还需要打区间赋值的tag，我就没有实现出来（？？？）。现在想想属实弱智。首先区间赋值的tag可以变成*0，也可以把变成0的节点直接删掉，但是还是要维护$kx+b$的tag的下传和合并（虽然也不难是吧）。实际上我也想过直接用正常的状态转移，但是没有想到前缀和怎么合并。。。实际上只需要在线段树合并的时候维护一个前缀和就好了，这样就只需要维护一个区间乘的tag了。how stupid i am! #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define maxn 500005 #define ll long long #define mo 998244353 #define maxm 20000005 using namespace std; int n,m,i,j,k,dep[maxn],q[maxn]; int em,e[maxn*2],nx[maxn*2],ls[maxn]; void read(int &x){ x=0; char ch=getchar(); for(;ch<'0'||ch>'9';ch=getchar()); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; } void insert(int x,int y){ em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; } int tot,M,tl[maxm],tr[maxm],rt[maxn]; ll t[maxm],tag[maxm],s1,s2; void dfs(int x,int p){ dep[x]=dep[p]+1,M=max(M,dep[x]); for(int i=ls[x];i;i=nx[i]) if (e[i]!=p) dfs(e[i],x); } int newnode(){tot++,t[tot]=0,tag[tot]=1;return tot;} void downtag(int x){ t[x]=t[x]*tag[x]%mo; if (tl[x]) tag[tl[x]]=tag[tl[x]]*tag[x]%mo; if (tr[x]) tag[tr[x]]=tag[tr[x]]*tag[x]%mo; tag[x]=1; } void add(int &x,int l,int r,int p,ll d){ if (!x) x=newnode(); if (tag[x]!=1) downtag(x); (t[x]+=d)%=mo; if (l==r) return; int mid=(l+r)>>1; if (p<=mid) add(tl[x],l,mid,p,d); else add(tr[x],mid+1,r,p,d); } void change(int x,int l,int r,int L,int R,ll v){ if (x&&tag[x]!=1) downtag(x); if (!x||l>R||r<L) return; if (L<=l&&r<=R) {tag[x]=tag[x]*v%mo;downtag(x);return;} int mid=(l+r)>>1; change(tl[x],l,mid,L,R,v); change(tr[x],mid+1,r,L,R,v); t[x]=(t[tl[x]]+t[tr[x]])%mo; } ll find(int x,int l,int r,int L,int R){ if (!x||l>R||r<L) return 0; if (tag[x]!=1) downtag(x); if (L<=l&&r<=R) return t[x]; int mid=(l+r)>>1; return find(tl[x],l,mid,L,R)+find(tr[x],mid+1,r,L,R); } void merge(int x,int y,int l,int r){ if (tag[x]!=1) downtag(x); if (tag[y]!=1) downtag(y); if (l==r) {(s1+=t[x])%=mo,(s2+=t[y])%=mo,t[x]=(t[x]*s2+t[y]*s1-t[x]*t[y])%mo;return;} int mid=(l+r)>>1; if (tl[x]&&tl[y]) merge(tl[x],tl[y],l,mid); else{ if (tl[x]&&!tl[y]) (s1+=t[tl[x]]*tag[tl[x]])%=mo,tag[tl[x]]=tag[tl[x]]*s2%mo; else if (!tl[x]&&tl[y]) (s2+=t[tl[y]]*tag[tl[y]])%=mo,tag[tl[y]]=tag[tl[y]]*s1%mo,tl[x]=tl[y]; } if (tr[x]&&tr[y]) merge(tr[x],tr[y],mid+1,r); else{ if (tr[x]&&!tr[y]) (s1+=t[tr[x]]*tag[tr[x]])%=mo,tag[tr[x]]=tag[tr[x]]*s2%mo; else if (!tr[x]&&tr[y]) (s2+=t[tr[y]]*tag[tr[y]])%=mo,tag[tr[y]]=tag[tr[y]]*s1%mo,tr[x]=tr[y]; } t[x]=(t[tl[x]]*tag[tl[x]]+t[tr[x]]*tag[tr[x]])%mo; } void dfs2(int x,int p){ add(rt[x],0,M,0,1); for(int i=ls[x];i;i=nx[i]) if (e[i]!=p){ dfs2(e[i],x); s1=s2=0,merge(rt[x],rt[e[i]],0,M); } if (q[x]) { add(rt[x],0,M,q[x],find(rt[x],0,M,0,q[x]-1)); change(rt[x],0,M,0,q[x]-1,0); } if (x>1){ add(rt[x],0,M,0,t[rt[x]]*tag[rt[x]]%mo); change(rt[x],0,M,dep[x]-1,dep[x]-1,0); } } int main(){ // freopen("ceshi.in","r",stdin); freopen("destiny.in","r",stdin); freopen("destiny.out","w",stdout); read(n); for(i=1;i<n;i++) read(j),read(k),insert(j,k); dfs(1,0),read(m); for(i=1;i<=m;i++) read(j),read(k),q[k]=max(q[k],dep[j]); dfs2(1,0); printf("%lld\n",(t[rt[1]]*tag[rt[1]]%mo+mo)%mo); }