BZOJ4033 [HAOI2015] T1 【树形dp】

tonyfang posted @ 2016年9月06日 21:49 in BZOJ with tags c++ oi , 1388 阅读




$f_{i, j}$表示以$i$为根的子树选$j$个,$i$为根的子树内的贡献加上$(i, fa_i)$的贡献的最大值。



# include <stdio.h>
# include <algorithm>
using namespace std;

typedef long long ll;

int n, k;
ll f[2010][2010], g[20010];
int tot=0, head[200010], next[200010], to[200010], sz[200010], w[200010];
inline void add(int u, int v, int tw) {
	next[tot] = head[u];
	head[u] = tot;
	to[tot] = v;
	w[tot] = tw;

inline void dfs(int x, int fa, int v) {
	int siz = 1;
	for (int I=head[x]; I; I=next[I]) {
		if(to[I] == fa) continue;
		dfs(to[I], x, w[I]);
		int newsz = siz + sz[to[I]];
		for (int i=0; i<=newsz && i<=k; ++i) g[i] = 0;
		for (int i=0; i<=siz && i<=k; ++i) {
			for (int j=0; j<=sz[to[I]] && j<=k; ++j) {
				if(i+j>k) continue;
				g[i+j] = max(g[i+j], f[x][i] + f[to[I]][j]);
		for (int i=0; i<=newsz && i<=k; ++i) f[x][i] = g[i];
		siz = newsz;
	sz[x] = siz;
	for (int i=0; i<=siz && i<=k; ++i) {
		if(siz + (k-i) > n) {
			f[x][i] = -666666666;
		f[x][i] += (ll)i*(k-i)*v;
		f[x][i] += (ll)(siz-i)*(n-siz-k+i)*v;

int main() {
	scanf("%d%d", &n, &k);
	for (int i=1, u, v, tw; i<n; ++i) {
		scanf("%d%d%d", &u, &v, &tw);
		add(u, v, tw); add(v, u, tw);
	dfs(1, 0, 0);
	printf("%lld\n", f[1][k]);
	return 0;
How to Send View Onc 说:
2022年11月04日 21:23

WhatsApp application holds global significance, with millions of users utilizing the app for chatting and calling. The software is open for personal and business chats. WhatsApp contains unique features such as expression emojis, video calls, status, and text. How to Send View Once Photos and Videos on Whatsapp Today the Facebook-owned app has developed a new “view once” feature. The mode allows the user to view photos and views once/single view, and the content disappears.

how to pin your loca 说:
2022年12月16日 23:32

Dropped Pins are a useful Google Maps feature that allows you to save a location. If a location does not have an address or if the address is incorrect, you can mark it with a pin. Your pins will help you go back to these areas, how to pin your location and you may share them with friends to mark a gathering spot. This simple guide explained briefly Dropped Pins in Google Maps and How to Pin a Location and Remove a Pin.

PNB Net Banking 说:
2023年1月28日 23:48

Punjab National Bank is a popular yet most preferred National Bank in India, and the Net Banking service for the bank allows its customers to utilize different services online without investing in the branch. PNB Net Banking As the modern days are invoking with the technology, the services from Banks through their Net Banking feature are in good spike, and there are multiple benefits for the customer who does get the access to the PNB Net Banking service.

登录 *

loading captcha image...
or Ctrl+Enter