Company

第一行输入两个数n(1 <= n <= 200000)村庄的数量，以及劳动力的评估标准k(1 <= k <= 1e9)
第二行有n个数，表示这n个村庄的村民数(1 <= a <= 1e9)
之后有n-1行，每行两个数字u, v（1 <= u, v <= n) u, v两个村庄之间有一条水管。

C++14(g++5.4) 解法, 执行用时: 184ms, 内存消耗: 6732K, 提交时间: 2018-12-30 14:29:02

#include <cstdio>

int i,n,k,p,a,b,t;
int pi[200001],pp[200001],pl[400001][2],ps[200001];
bool pf[200001];

void sou(int t)
{
	int i=pp[t];
	pf[t]=true;
	while(i!=0)
	{
		if(pf[pl[i][0]]==false)
		{
			sou(pl[i][0]);
			ps[t]+=ps[pl[i][0]];
		}
		i=pl[i][1];
	}
	if(pi[t]<=k) ps[t]++;
	return;
}

int main()
{
	scanf("%d%d",&n,&k);
	for(i=1; i<=n; i++) scanf("%d",&pi[i]);
	for(i=1; i<n; i++)
	{
		scanf("%d%d",&a,&b);
		pl[++t][0]=b;
		pl[t][1]=pp[a];
		pp[a]=t;
		pl[++t][0]=a;
		pl[t][1]=pp[b];
		pp[b]=t;
	}
	sou(1);
	for(i=1; i<=n; i++) printf("%d ",ps[i]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 347ms, 内存消耗: 56164K, 提交时间: 2020-02-18 14:05:24

#include<bits/stdc++.h>
using namespace std;
int n,m,d[200005]={0};
vector<int>g[2000005];
void dfs(int x,int fa)
{
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		if(y==fa) continue;
		dfs(y,x);
		d[x]+=d[y];
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(x<=m) d[i]++;
		
	}
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x); 
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	printf("%d ",d[i]);
	return 0;
}

详情