cf C. Vertex Deletion 树形DP 删除某写节点 且保证其它节点都有至少一个相连节点的总方案数

标签：contains 删除 ll 某写 Vertex 节点 dp mod

 https://codeforces.com/gym/103145/problem/C

  time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output

Given a tree with nn vertices, you can delete any vertex you like. We call a way of deletion beautiful if, in the remaining part of the tree, every vertex has at least one vertex still connected to it. You need to calculate how many ways of deletion are beautiful.

Two ways of deletion are considered the same if the set of the deleted vertex is the same.

Input

This problem contains multiple test cases.

The first line contains an integer TT indicating the number of test cases.

For each test case, the first line contains one integer nn (1≤n≤1051≤n≤105).

The next n−1n−1 lines each contains two integers uu and vv (1≤u,v≤n,u≠v1≤u,v≤n,u≠v), representing an edge (u, v).

It's guaranteed that ∑n≤106∑n≤106.

Output

Output TT lines, each line contains an integer indicating the answer.

Since the answer can be very large, you only need to output the answer modulo 998244353998244353.

Example input Copy

1
6
1 2
1 3
2 4
2 5
3 6

output Copy

22

分析

递推，求删除某些点，不会导致每个点没有相邻的点的数目

在树上操作，所以树形dp，lca之类的。。

这题明显不是lca，只能是树形DP

可以想到设两个状态：

dp[u][0]表示删除u点

dp[u][1]表示不删除u点

但是光这两个状态，没法看出，删除当前点，子节点有没有被孙子节点连接

所以当前点的状态不光要保存当且点，还要保存子节点的信息。

 

设状态：

dp[u][0]表示删除u

dp[u][1] 表示不删除u，但删除u的所有子节点

dp[u][2] 表示不删除u，但给u留一个子节点

这样就可以表示当前点的子节点有没有被节点连接了

状态转移：(v是子节点)

dp[u][0] *= (dp[v][2] + dp[v][0])

dp[u][1] *= (dp[v][0])

dp[u][2] *= (dp[v][1] + dp[v][2] + dp[v][0]) 且 最后dp[u][2] -= dp[u][1] ，容斥原理，当前点如果保留，子节点，那子节点可以是三种情况中的任何一种，但是维独不能是所有子节点都被删除

 

//-------------------------代码----------------------------

//#define int ll
const int N = 1e5+10,mod = 998244353;
int n,m;
ll f[N][3];
V<int> e[N];

//f[u][0] 表示当前节点被删除
//f[u][1] 表示当前节点没被删除,且删去所有子节点 
//f[u][2] 表示当前点没删除，且保留一个以上子节点 

void dfs(ll u,ll fa) {
    db(u);
    f[u][0] = f[u][1] = f[u][2] = 1;//初始化
    for(auto v:e[u]) {
        if(v == fa) continue;
        dfs(v,u);
        f[u][0] = (f[v][0] + f[v][2]) % mod * f[u][0] % mod;
        f[u][1] = f[v][0] * f[u][1] % mod;
        f[u][2] = (f[v][0] + f[v][1] + f[v][2]) % mod * f[u][2] % mod;
    } 
    f[u][2] = (f[u][2] - f[u][1] + mod) % mod;
} 

void solve()
{
    ms(f,0);
//    cin>>n>>m;
    cin>>n;
    fo(i,1,n) e[i].clear(); 
    fo(i,1,n-1) {
        int a,b;cin>>a>>b;
        e[a].push_back(b);e[b].push_back(a);
    }
    dfs(1,-1);
    ll res = ((f[1][0]+f[1][2])) % mod;
    cout<<res<<endl;
     
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

标签：contains,删除,ll,某写,Vertex,节点,dp,mod
From： https://www.cnblogs.com/er007/p/16590022.html