The 15th Chinese Northeast Collegiate Programming Contest C. Vertex Deletion(树形dp)

简介: The 15th Chinese Northeast Collegiate Programming Contest C. Vertex Deletion(树形dp)

linkkkk

题意:

给出一棵树,每次可以删去任意点,要求删完后不能有孤立的点,求方案数。

思路:

大概很容易看出来是个树形dp,状态不太好想。

d p [ u ] [ 0 ]表示删去这个点

d p [ u ] [ 1 ]表示不删这个点,而且删去所有子节点

d p [ u ] [ 2 ] 表示不删这个点,而且至少留一个子节点

对于第一种情况,此时的u一定满足条件;

对于第二种情况,要求u的父亲节点也不被删去才可以满足条件;

对于第三种情况,此时的u已经满足条件了。

转移的话:

dp[u][0]=(dp[t][0]+dp[t][2])%mod*dp[u][0]%mod;
dp[u][1]=dp[u][1]*dp[t][0]%mod;

如果删去u的话,那么想让子节点t满足条件,可以删除t,也可以不删t并且至少保留t的一个子节点;

如果不删u并且删去所有子节点的话,说明节点t是被删除的状态。

对于d p [ u ] [ 2 ]可以用所有合法的方案数减去不合法的方案数。

最后答案就是d p [ 1 ] [ 0 ] + d p [ 1 ] [ 2 ]

代码:

const int maxn=1e5+7,inf=0x3f3f3f3f;
const ll mod=998244353;
const double eps=1e-5;
vector<int>g[maxn];
ll dp[maxn][3],n;
void dfs(int u,int fa){
  dp[u][0]=dp[u][1]=dp[u][2]=1;
  for(auto t:g[u]){
    if(t==fa) continue;
    dfs(t,u);
    dp[u][0]=(dp[t][0]+dp[t][2])%mod*dp[u][0]%mod;
    dp[u][1]=dp[u][1]*dp[t][0]%mod;
    dp[u][2]=(dp[t][0]+dp[t][2]+dp[t][1])%mod*dp[u][2]%mod; 
  }
  dp[u][2]=(dp[u][2]-dp[u][1])%mod;
}
int main(){
  int _=read;
  while(_--){
    n=read;
    rep(i,1,n-1){
      int u=read,v=read;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    dfs(1,-1);
    ll ans=dp[1][0]+dp[1][2];
    ans=(ans+mod)%mod;
    printf("%d\n",ans);
    rep(i,1,n) g[i].clear(),dp[i][0]=dp[i][1]=dp[i][2]=0;
  }
    return 0;
}
目录
打赏
0
0
0
0
108
分享
相关文章
English Contest -- The Programmer&#39;s Dream
<p></p> <p>Yes, The Programmer’s Dream!</p> <p>How many programmers here? I am sure of that every body here has a dream inside. What’s the biggest dream or goal you have in your life at this mom
1722 0
[Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.5.7
Prove that for any vectors $$\bex u_1,\cdots,u_k,\quad v_1,\cdots,v_k, \eex$$ we have $$\bex |\det(\sef{u_i,v_j})|^2 \leq \det\sex{\sef{u_i,u_j}}\cdot...
618 0
[Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.5.1
Show that the inner product $$\bex \sef{x_1\wedge \cdots \wedge x_k,y_1\wedge \cdots\wedge y_k} \eex$$ is equal to the determinant of the $k\times k$ matrix $\sex{\sef{x_i,y_j}}$.
639 0
[Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.5.9
(Schur's Theorem) If $A$ is positive, then $$\bex \per(A)\geq \det A. \eex$$   Solution. By Exercise I.
570 0
[Bhatia.Matrix Analysis.Solutions to Exercises and Problems]PrI.6.1
Given a basis $U=(u_1,\cdots,u_n)$ not necessarily orthonormal, in $\scrH$, how would you compute the biorthogonal basis $\sex{v_1,\cdots,v_n}$? Find ...
700 0
[Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.5.3
Let $\scrM$ be a $p$-dimensional subspace of $\scrH$ and $\scrN$ its orthogonal complement. Choosing $j$ vectors from $\scrM$ and $k-j$ vectors from $...
737 0
[Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.5.4
If $\dim \scrH=3$, then $\dim \otimes^3\scrH =27$, $\dim \wedge^3\scrH =1$ and $\dim \vee^3\scrH =10$.
719 0
[Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.5.2
The elementary tensors $x\otimes \cdots \otimes x$, with all factors equal, are all in the subspace $\vee^k\scrH$.
460 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等