列表

详情

NC229813. 灵力之泉

描述

传说中，天井下是一种藏在屋檐下的妖怪，她可以在屋檐之间传输灵力。

天井下常驻的屋檐共有 n 个，依次标号为 。屋檐之间有 n-1 条双向小路连接，且从任意屋檐出发，天井下总能沿着小路移动到另一个屋檐下。

现在，天井下可以任选一个屋檐，在该屋檐下放置灵力之泉。时刻 时，只有拥有灵力之泉的屋檐充满灵力。每一个时刻 t 时，若屋檐 u 充满灵力，那么天井下可以任选至多 w_u 个与屋檐 u 有小路直接相连的屋檐，并让这些屋檐在 时刻充满灵力。

天井下希望让每个屋檐都充满灵力，并且达成该条件的时刻越早越好，但是她还没有确定选择在哪个屋檐下放置灵力之泉。请你计算分别在屋檐 下放置灵力之泉，达成条件的最早时刻是多少。

输入描述

第一行为一个用空格分隔的整数 n ()，表示屋檐的个数。

第二行为 n 个用空格分隔的整数 （）。

接下来的 n-1 行，每行两个整数 u, v ()，表示屋檐 u, v 之间有一条双向小路连接。

保证屋檐的连接情况满足：从任意屋檐出发，天井下总能沿着小路移动到另一个屋檐下。

输出描述

输出 n 行，每行输出一个整数，其中第 i 行的数表示在屋檐 i 下放置灵力之泉，达成条件的最早时刻。

示例1

输入: 

4
1 1 1 1
1 2
1 3
3 4

输出: 

2
3
2
3

说明:

在屋檐 1 下放置灵力之泉时，各时刻拥有灵力的屋檐编号如下：

1. t = 0：\{1\}
2. t = 1：\{1, 3\}
3. t = 2：\{1, 2, 3, 4\}

在屋檐 2 下放置灵力之泉时，各时刻拥有灵力的屋檐编号如下：

1. t = 0：\{2\}
2. t = 1：\{1, 2\}
3. t = 2：\{1, 2, 3\}
4. t = 3：\{1, 2, 3, 4\}

在屋檐 3 下放置灵力之泉时，各时刻拥有灵力的屋檐编号如下：

1. t = 0：\{3\}
2. t = 1：\{1, 3\}
3. t = 2：\{1, 2, 3, 4\}

在屋檐 4 下放置灵力之泉时，各时刻拥有灵力的屋檐编号如下：

1. t = 0：\{4\}
2. t = 1：\{3, 4\}
3. t = 2：\{1, 3, 4\}
4. t = 3：\{1, 2, 3, 4\}

示例2

输入: 

7
1 2 3 1 5 3 4
2 3
4 3
7 3
1 6
1 5
5 7

输出: 

4
5
4
5
3
5
3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 340ms, 内存消耗: 69600K, 提交时间: 2022-01-08 03:48:51 

#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m,t,a[200500],f[200500],g[200500];
vector<int> v[200500];
vector<pair<int,int> >v0[200500];
void dfs(int x,int fa){
	int t1=0;
	for(auto i:v[x]){
		if(i==fa)continue;
		dfs(i,x);
		v0[x].push_back({-f[i],i});
	}
	sort(v0[x].begin(),v0[x].end());
	for(auto [i,j]:v0[x]){
		i=-i;f[x]=max(f[x],t1/a[x]+1+i);t1++;
	}
}
void dfs2(int x,int fa,int lst){
	int t1=0;
	vector<pair<int,int> > v2=v0[x];
	if(x==1)g[x]=f[x];
	else{
		v2.push_back({-lst,fa});
		sort(v2.begin(),v2.end());
		for(auto [i,j]:v2){
			i=-i;g[x]=max(g[x],t1/a[x]+1+i);t1++;
		}
	}
	set<pair<int,int> >s;
	t1=-1;
	for(auto [i,j]:v2){
		i=-i;s.insert({-((t1/a[x])+1+i),j});t1++;
	}
	t1=0;
	for(auto [i,j]:v2){
		i=-i;
		s.erase({-(((t1-1)/a[x])+1+i),j});
		if(j!=fa)dfs2(j,x,-(*s.begin()).first);
		s.insert({-(((t1)/a[x])+1+i),j});
		t1++;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<n;i++){
		cin>>j>>k;
		v[j].push_back(k);
		v[k].push_back(j);
	}
	dfs(1,0);
	dfs2(1,0,0);
	for(i=1;i<=n;i++)cout<<g[i]<<'\n';
}

上一题

© 2024 nowcoder.com