[nk] 牛客月赛45 E.筑巢

前言

传送门 :

思路

标签 : 树形 d p dp dp

状态表示 : f [ i ] f[i] f[i], 以 i i i为树根的最大舒适度 状态计算 : f [ i ] = m a x ( f [ i ] , f [ j ] + w [ i ] + f [ i ] ) f[i] =max(f[i],f[j]+w[i]+f[i]) f[i]=max(f[i],f[j]+w[i]+f[i])

记得开 l l ll ll

Mycode

void dfs(int u){
	if(st[u]) return;
	st[u] = 1;
	f[u] += a[u];
	
	for(auto x : g[u]){
		if(st[x.to])  continue;
		dfs(x.to);
		f[u] =  max(f[u],f[u]+f[x.to]+x.val);
	}
}

void solve()
{
	cin>>n;
	for(int i=1;i>a[i];
	
	for(int i=1;i>a>>b>>c;
		g[a].pb({b,c});
		g[b].pb({a,c});
	}
	
	
	for(int i=1;i