P5007 DDOSvoid 的疑惑 题解

题目传送门

思路

树形 dp 模版题。

设 \(dp_i\) 为 \(pos\) 的最优解，\(dp2_i\) 为只考虑 \(pos\) 子树时，毒瘤集的数量。

可得：
\(dp_i=dp_{i}\times dp2_{son}+dp_{son}\times dp2_{i}+dp_i+dp_{son}\)
\(dp2_i=dp2_{i}\times dp2_{son}+dp2_{i}+dp2_{son}\)

用深搜来更新 \(dp\) 数组即可。

代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=100000007;
vector<int>g[1140000];
long long dp[1140000],dp2[1140000],n,w[1140000],x,y,key;
void dfs(int pos,int f) {
	for (int i=0; i<g[pos].size(); i++) {
		int t=g[pos][i];
		if (t!=f) {
			dfs(t,pos);
			dp[pos]=(dp[t]*dp2[pos]+dp[pos]*dp2[t]+dp[pos]+dp[t])%mod;
			dp2[pos]=(dp2[pos]+dp2[t]*dp2[pos]+dp2[t])%mod;
		}
	}
	dp[pos]=(long long)(pow(pos,key)+dp[pos])%mod;
	dp2[pos]=(dp2[pos]+1)%mod;
	return;
}
int main() {
	cin>>n>>key;
	for(int i=1; i<n; i++) {
		cin>>x>>y;
		g[y].push_back(x);
		g[x].push_back(y);
	}
	dfs(1,0);
	cout<<dp[1];//最后的答案是 dp[1]
}