题解：P10894 虚树

· · 题解

首先考虑求出整棵树的方案数，因为某一子树内的虚树形态对父节点而言不重要，使用树形 dp 经典思路：令 dp_i 表示以 i 为根的方案，然后对于每一个点，考虑它选或不选分别的贡献：如果这个点选了，那么它的不同子树方案可以自由组合，而如果它没有选，那么它的不同子树方案就是互斥的，因为它们的 \text{lca} 没选。二者分别对应乘法和加法原理，然后加起来即可

dp_i=\prod(dp_{son_i}+1)+\sum{dp_{son_i}}

求出整棵树后，面临删子树的询问，你发现每个节点的 dp 值显然只会对其祖先有影响。于是每次修改到根并获得了 30 分的好成绩。而观察上式,发现 dp_i 对 dp_{f_i} 的贡献正好是 dp_i \times (\prod(dp_{bro_i}+1)+1)（bro_i 指 i 的兄弟节点），该因子可在处理父节点时同时维护，所以我们可以使用前缀积，O(n) 处理出每个节点的 dp_i 对根的贡献 g_i,询问时输出 dp_1-dp_i \times g_i 即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long p=998244353,f[500011],hd[500011],nt[1000011],cnt=0,b[1000011],m=1,dp[500001][4];
inline long long add(long long x,long long y){return x+y>=p?x+y-p:x+y;}
inline void addln(long long x,long long y){
    nt[++m]=hd[x],b[m]=y,hd[x]=m;
    nt[++m]=hd[y],b[m]=x,hd[y]=m;}
inline long long ksm(long long x,long long y){
    long long k=1,l=x;
    while(y){if(y&1)k=k*l%p;l=l*l%p,y>>=1;}
    return k;
}
inline long long rd(){
    long long i=0,j=1;char g=getchar();
    while(g>57||g<48){if(g=='-')j=-1;g=getchar();}
    while(g>47&&g<58)i=(i<<3)+(i<<1)+g-48,g=getchar();
    return i*j;
}
inline void dfs(long long x,long long y){
    cnt++;f[x]=y;
    for(int i=hd[x];i;i=nt[i])if(b[i]!=y){
        dfs(b[i],x);
        dp[x][1]=dp[x][1]*(dp[b[i]][2]+1)%p,dp[x][0]=add(dp[x][0],dp[b[i]][2]);
    }dp[x][2]=add(dp[x][1],dp[x][0]);
    for(int i=hd[x];i;i=nt[i])if(b[i]!=y)
        dp[b[i]][3]=(dp[x][1]*ksm(dp[b[i]][2]+1,p-2)+1)%p; 
}
inline void dfs1(long long x,long long y){
    if(y>1)dp[x][3]=dp[x][3]*dp[y][3]%p;
    for(int i=hd[x];i;i=nt[i])
        if(b[i]!=y)dfs1(b[i],x);
}
inline void sol(){
    long long i,j,k,n=rd(),q,ans,u,v,t;m=1;
    for(i=1,dp[n][1]=1;i<n;i++){
        dp[i][1]=1;
        u=rd(),v=rd();addln(u,v);}dfs(1,0);
    dfs1(1,0);t=rd();
    while(t--){q=rd();
        ans=q==1?0:add(dp[1][2],p-dp[q][3]*dp[q][2]%p);
        printf("%lld\n",ans);
    }
}
int main()
{   sol();
    return 0;
}