xdoj 1070 Eddy’s network system(简单树dp)

2019-07-11 by fffasttime·0评论

n个节点的树中选出m个点的子树，使子树的点权和最大。

树背包模板题。合并子树的时候枚举到子树大小就够了，这样保证每个点被，是O(n^2)的。

```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
#define inc(i,n) for (int i=0;i<n;i++)
```

#define dec(i,n) for (int i=n-1;i>=0;i--)

```
int a[110][110];
```
```
vector<int> ed[110];
```
```
int n,m; 
```
```
void dfs(int u, int f){
```
```
	for (int i=0;i<ed[u].size();i++){
```
```
		int v=ed[u][i];
```
```
		if (v^f){
```
```
			dfs(v,u);
```
```
			dec(j,n+1){
```
```
				inc(k,j)
```

				a[u][j]=max(a[u][j],a[u][j-k]+a[v][k]);

```
			}
```
```
		}
```
```
	}
```
```
}
```
```
 
```
```
int main(){
```
```
	int T; cin>>T;
```
```
	while (T--){
```
```
		memset(a,0xC0,sizeof a);
```
```
		cin>>n>>m; 
```

		inc(i,n) scanf("%d",a[i]+1),ed[i].clear();

```
		inc(i,n-1){
```
```
			int x,y; scanf("%d%d",&x,&y);
```
```
			ed[x].push_back(y);
```
```
			ed[y].push_back(x);
```
```
		}
```
```
		dfs(0,-1);
```
```
		int ans=0;
```
```
		inc(i,n) ans=max(ans,a[i][m]);
```
```
		cout<<ans<<'\n';
```
```
	}
```
```
	return 0;
```
```
}
```

发表评论取消回复