【HDU5647 BestCoder Round 76 (div1)B】【树形DP】DZY Loves Connecting 一棵树的所有生成子树的大小乘积

本文主要是介绍【HDU5647 BestCoder Round 76 (div1)B】【树形DP】DZY Loves Connecting 一棵树的所有生成子树的大小乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DZY Loves Connecting

Accepts: 16

Submissions: 169

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

问题描述

DZY有一棵 $n$ 个结点的无根树，结点按照 $1\sim n$ 标号。DZY喜欢树上的连通集。一个连通集 $S$ 是由一些结点组成的集合，满足 $S$ 中任意两个结点 $u, v$ 能够用树上的路径连通，且路径上不经过 $S$ 之外的结点。显然，单独一个结点的集合也是连通集。一个连通集的大小定义为它包含的结点个数，DZY想知道所有连通集的大小之和是多少。你能帮他数一数吗？答案可能很大，请对 $10^9 + 7$ 取模后输出。

输入描述

第一行 $t$ ，表示有 $t$ 组数据。
接下来 $t$ 组数据。每组数据第 $1$ 行一个数 $n$ 。第 $2\sim n$ 行中，第 $i$ 行包含一个数 $p_i$ ，表示 $i$ 与 $p_i$ 有边相连。( $1\le p_i \le i-1,2\le i\le n$ )( $n\ge 1$ ，所有数据中的 $n$ 之和不超过 $200000$ )

输出描述

每组数据输出一行答案，对 $10^9 + 7$ 取模。

输入样例

输出样例

1
42

Hint

第二个样例中，树的4条边分别为(1,2),(2,3),(2,4),(3,5)。所有连通集分别是{1},{2},{3},{4},{5},{1,2},{2,3},{2,4},{3,5},{1,2,3},{1,2,4},{2,3,4},{2,3,5},{1,2,3,4},{1,2,3,5},{2,3,4,5},{1,2,3,4,5}。

If you need a larger stack size, 
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 2e5+10, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
LL sum[N];	//sum[i]表示以i为根节点的所有可能的子树大小之和
LL num[N];	//num[i]表示以i为根节点的子树方案
int n, x;
vector<int>a[N];
LL ans;
void dfs(int x,int fa)
{num[x] = 1;sum[x] = 1;for (int i = a[x].size() - 1; ~i; --i){int y = a[x][i];if (y == fa)continue;dfs(y, x);sum[x] = (sum[x] * (num[y] + 1) + sum[y] * num[x]) % Z;num[x] = num[x] * (num[y] + 1) % Z;}ans = (ans + sum[x]) % Z;
}
int main()
{scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){scanf("%d", &n);for (int i = 1; i <= n; ++i)a[i].clear();for (int i = 2; i <= n; ++i){scanf("%d", &x);a[i].push_back(x);a[x].push_back(i);}ans = 0;dfs(1, 0);printf("%lld\n", ans);}return 0;
}
/*
【trick&&吐槽】
1，BC会爆栈BC会爆栈BC会爆栈BC会爆栈BC会爆栈BC会爆栈BC会爆栈
2，不论是用费马小定理求逆元还是拓展欧几里得求逆元，都要注意要使得gcd()==1这里不光要要求模数Z为素数。因为只是涉及到乘法还无所谓，很多时候还涉及到加法，这就可能会使得方案数为Z的倍数。于是我们要尽量避免求逆元运算。
3，留时间制造hack数据>_<，比如爆栈啦，比如子树的形态构建啦【题意】
一棵树n(2e5)个节点，问所有子树size的乘积。【类型】
树形DP【分析】
首先因为是棵树，所以不妨以1为父节点。
然后我们发现，总归要有一个节点为整棵子树的根节点的。
于是，我们枚举一个点为子树的根节点，然后求其为子树根节点时的子树的大小之和以及子树个数
定义：LL sum[N];	//sum[i]表示以i为根节点的所有可能的子树大小之和LL num[N];	//num[i]表示以i为根节点的子树方案
显然答案就是∑sum[]。然而这个DP要怎么展开呢？
void dfs(int x,int fa)
{num[x] = 1;//只算x作为根节点时的自己，方案数为1sum[x] = 1;//只算x作为根节点时的自己，子树大小和为1for (int i = a[x].size() - 1; ~i; --i){int y = a[x][i];if (y == fa)continue;dfs(y, x);//之前子树的大小会变成*(num[y]+1)种可行方案//新的子树(y)大小会变成sum[y]*num[x]种可行方案sum[x] = (sum[x] * (num[y] + 1) + sum[y] * num[x]) % Z;//子树方案会变成*(num[y]+1)种num[x] = num[x] * (num[y] + 1) % Z;}ans = (ans + sum[x]) % Z;
}
【时间复杂度&&优化】
O(n)*/

这篇关于【HDU5647 BestCoder Round 76 (div1)B】【树形DP】DZY Loves Connecting 一棵树的所有生成子树的大小乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！