刷题记录:牛客NC51180Accumulation Degree

传送门:牛客

题目描述:

Trees also play an intimate role in many of the world's mythologies. Many scholars are interested in finding peculiar properties about trees, such as the center of a tree, tree counting, tree coloring. A(x) is one of such properties.
A(x) (accumulation degree of node x) is defined as follows:
Each edge of the tree has an positive capacity.
The nodes with degree of one in the tree are named terminals.
The flow of each edge can't exceed its capacity.
A(x) is the maximal flow that node x can flow to other terminal nodes.
Since it may be hard to understand the definition, an example is showed below:
输入:
1
5
1 2 11
1 4 13
3 4 5
4 5 10
输出:
26
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

一道经典的换根dp的题目.

主要思路:

1. 首先根据换根dp的经典思路.我们显然可以先使用$d[u]$来记录我们的每一个根节点$u$的最大流量值.那么定好我们的dp方程时候,我们的转移方程也是十分好写的.当前的流量的最大值,显然是通向每一个儿子节点的流量的和,那么这个值其实就是我们的$min(d[v],w)$,也就是如果我们的u与v之间的可流通量大于我的v节点的最大流通量的话,那么显然我们是可以满足我们的子节点的流通量的,所以直接加上我们的子节点的流通量,反之即使我们的子节点的流通量再大,我们也通不过去,所以被限制在了路径流通量之中.并且需要注意的是,此处我们是需要特判的,也就是当我们的v没有儿子时,此时$d[v]$显然是0,但是我们的可流通量应该是路径值
2. 但是显然的,我们并没有解决我们的问题,因为我们只是解决了每一个根节点的最大流通量,但是这个父子关系是我们自己定的.题目中需要我们去求的不只是该节点的儿子节点的流通量,还有我们的父亲节点那边的流通量,所以我们需要求出我们的父亲节点那边的流通量.所以我们可以使用换根dp的思想去解决这个问题.我们使用$dp[u]$来记录我们的$u$节点的最大流量值,注意此时的数组记录的不仅是自己儿子的,还有自己父亲的,和之前是不同的.那么我们想一下,我们的u节点流向我们的v节点的流星为$min(d[v],tree[u][i].w)$,那么假设我们使用$dp[u]$减去流向v节点的流量,剩下的不就是u能流向我们的其他节点的流量.我们在将这个值与我们的$tree[u][i].w$比较一下,跟之前说的一样,假设我们的这个值大于路径值的话,显然会被限制,反之则不会.所以取一下min累加一下即可

至此,我们的换根dp结束了

注意使用longlong

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
#define int ll
int min(int a,int b) {return a>b?b:a;}
int n,k;
int dp[2500][2500];
vector<int>tree[3000];
int ans=0;
const int mod=998244353;int size_tree[maxn];
void dfs(int u,int pre_u) {
	dp[u][1]=1;size_tree[u]=1;
	for(int i=0;i<tree[u].size();i++) {
		int v=tree[u][i];
		if(v==pre_u) continue;
		dfs(v,u);int sum=0;
		for(int j=1;j<=min(size_tree[v],k);j++) {//记录删边时子树的情况
			sum=(sum+dp[v][j])%mod;
		}
		for(int vu=min(size_tree[u],k);vu>=1;vu--) {
			for(int vv=min(size_tree[v],k);vv>=1;vv--) {
				if(vv+vu<=k) dp[u][vv+vu]=(dp[u][vu+vv]+dp[u][vu]*dp[v][vv]%mod)%mod;
			}
			dp[u][vu]=dp[u][vu]*sum%mod;
		}
		size_tree[u]+=size_tree[v];
	}
	return ;
}
signed main() {
	n=read();k=read();int u,v;
	for(int i=1;i<n;i++) {
		u=read();v=read();
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	dfs(1,0);
	for(int i=1;i<=k;i++) {
		ans=(ans+dp[1][i])%mod;
	}
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66