灵力之泉

灵力之泉

https://ac.nowcoder.com/acm/contest/11196/C

换根dp{dp}.

首先我们假如知道子树相连点的答案,我们肯定优先选择最大的.

dpdp方程为:fu=max(fu,fv+i/wu+1).f_u=max(f_u,f_v+i/w_u+1). ii表示第i大的fvf_v.

通过树形dpdp转移后.那么紧接着就是换根dpdp了,考虑如何通过父亲节点得到子节点的答案,可以通过前后缀的形式,我通过把父亲节点的所有子节点做个前缀和后缀,然后转移得到在这个节点当根节点时候,父亲节点相邻对它的贡献gug_u.

然后就解决了.

code:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int w[N],f[N],ans[N],pre[N],suf[N],g[N];
vector<int>G[N];

void dfs(int u,int fa)
{
	vector<int>temp;
	for(int v:G[u])
	{
		if(v==fa)	continue;
		dfs(v,u);
		temp.push_back(f[v]);
	}
	sort(temp.begin(),temp.end());
	reverse(temp.begin(),temp.end());
	for(int i=0;i<(int)temp.size();i++)
	{
		int v=temp[i];
		f[u]=max(f[u],v+i/w[u]+1);
	}
}

void DFS(int u,int fa)
{
	vector<pair<int,int> >temp;
	temp.push_back({g[u],u});
	for(int v:G[u])
	{
		if(v==fa)	continue;
		temp.push_back({f[v],v});
	}
	sort(temp.begin(),temp.end());
	reverse(temp.begin(),temp.end());
	int cnt=(int)temp.size();
	suf[cnt]=0;
	for(int i=cnt-1;i>=0;i--)
		suf[i]=max(suf[i+1],temp[i].first+(i-1)/w[u]+1);
	for(int i=0;i<cnt;i++)
	{
		pre[i]=temp[i].first+i/w[u]+1;
		if(i)	pre[i]=max(pre[i],pre[i-1]);
		if(temp[i].second!=u)
		{
			int x=temp[i].second;
			g[x]=suf[i+1];
			if(i)	g[x]=max(g[x],pre[i-1]);
		}
	}
	ans[u]=pre[cnt-1];
	//记录当i作为根节点 此时u中比它小的后缀最大值,因为i不算u的节点  
	for(int v:G[u])
	{
		if(v==fa)	continue;
		DFS(v,u);
	}
}

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,1);
	g[1]=-1;
	DFS(1,1);
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}

lpt的小屋 文章被收录于专栏

我想要一份甜甜的爱情

全部评论

相关推荐

06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务