自动搬运

查看原文

来自洛谷，原作者为

	z7z_Eta 今日も日が落ちて、夜が更けていく。

搬运于2025-08-24 22:18:37，当前版本为作者最后更新于2020-05-11 11:14:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

preface.

做法使用了树形dp一次dfs, 对 BeyondHeaven 的题解做了一定的简析与补充

提取题意.

• 选择一个$d$的联通子树(连通块), 并且选择一个点作入口. $d$ 是小 c 所在的结点.
• 入口 $r$ 满足 $deg_r \le k_r-1$ ; 其他点 $v$ 满足 $deg_v \le k_v$ .
• 求所有联通子树内的边权值和的最大价值.

官方题解的做法是令 $r$ 做根, 用换根dp解决问题

然而比赛时发现了一种更通用的做法, 直接将入口 $r$ 作为新的一维

• 我们以$d$为根, 状态记做$f[u][0/1]$
• 其中$f[u][0]$表示$u$子树中没有选择$r$的最大价值, $f[u][1]$则表示$u$子树中已选$r$

这样就保证了$d$在联通块内, 并且$r$被选到

于是, 题目变成了提高组dp

转移方程.

$f[u][0] = \text{前}k[u]-1\text{大的}\{f[v][0]+val_{(u,v)}\}$

$f[u][1] = \begin{cases} 1.\text{前}k[u]-2\text{大的}\{f[v][0]+val_{(u,v)}\}\\ 2.\max_{x} \{ f[x][1]+val_{(u,x)}+\text{除}x\text{之外前}k[u]-2\text{大的}\{f[v][0]+val_{(u,v)}\}\} \end{cases} $

($2.$) 转移$2.$本质是枚举了$x$中出现了入口$r$

注意当$k[u]=1$时, $f[u][1] = -\inf$, 因为没有可选的儿子

因为$d$是根, $k[d]$需要先$+1$

所求即为$f[d][1]$

else.

由于排序, 复杂度 $O(n \log n)$

在 BeyondHeaven 的题解中, $f[u][1]$的转移没有考虑$k[u]-1$之外的, 所以有些瑕疵

code:

// Etavioxy
#define il inline
#define ll long long
#define rep(i,s,t) for(register int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(register int i=(s);i>=(t);i--)
#define each(i,u) for(int i=head[u];i;i=bow[i].nxt)
#define pt(x) putchar(x)
using namespace std;
il int ci(){
	register char ch;int f=1;
	while(!isdigit(ch=getchar()))f=ch=='-'?-1:1;
	register int x=ch^'0';
	while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
	return f*x;
}

enum{N=100023};

struct Edge{ int nxt,to,val; } bow[N*2];
int head[N],tot_e;
il void add(int x,int y,int z){
	tot_e++;
	bow[tot_e<<1]=(Edge){head[x],y,z};
	bow[tot_e<<1|1]=(Edge){head[y],x,z};
	head[y]=(head[x]=tot_e<<1)|1;
}

int k[N];
int val[N],f[N][2];
bool cmp1(int x,int y){
	return f[x][0]+val[x] > f[y][0]+val[y];
}
void dfs(int u,int fa){
	if( k[u]==0 ){
		f[u][1] = -1e9;
		f[u][0] = 0;
		return ;
	}
	f[u][1] = f[u][0] = 0;
	vector<int>vec;
	each(i,u){
		int v = bow[i].to;
		if( v==fa ) continue;
		dfs(v,u);
		val[v] = bow[i].val;
		vec.push_back(v);
	}
	sort(vec.begin(),vec.end(),cmp1);
	bool flag=0;
	if( k[u]>(int)vec.size() ){ flag = 1; k[u] = vec.size(); }
	rep(i,0,k[u]-1) f[u][0] += f[vec[i]][0]+val[vec[i]];
	if( flag ) return f[u][1] = f[u][0], void();
	int kth = vec[k[u]-1];
	f[u][1] = f[u][0] - f[kth][0] - val[kth];
	rep(i,0,(int)vec.size()-1){
		if( i<=k[u]-1 ) f[u][1] = max(f[u][1],f[vec[i]][1]+f[u][0]-f[vec[i]][0]);
		else f[u][1] = max(f[u][1],f[vec[i]][1]+val[vec[i]]+f[u][0]-f[kth][0]-val[kth]);
	}
//	printf("LINE : %d u %d f %d %d\n",__LINE__,u,f[u][0],f[u][1]);
}

int main(){
	int n = ci(), d = ci();
	rep(i,1,n-1){
		int x = ci(), y = ci();
		add(x,y,ci());
	}
	rep(i,1,n) k[i] = ci()-1;
	k[d]++;
	dfs(d,0);
	printf("%d\n",f[d][1]);
	return 0;
}

这道题超优美的

但是Eta太蠢了太蠢了太蠢了