灵力之泉_牛客博客

换根 $d p$ .

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

$d p$ 方程为: $f_{u} = m a x (f_{u}, f_{v} + i / w_{u} + 1) .$ $i$ 表示第i大的 $f_{v}$ .

通过树形 $d p$ 转移后.那么紧接着就是换根 $d p$ 了,考虑如何通过父亲节点得到子节点的答案,可以通过前后缀的形式,我通过把父亲节点的所有子节点做个前缀和后缀,然后转移得到在这个节点当根节点时候,父亲节点相邻对它的贡献 $g_{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;
}