记录编号	535412	评测结果	AAAAAAAAAA
题目名称	原谅	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	1.537 s
提交时间	2019-07-04 22:43:51	内存使用	89.96 MiB

#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
map<pair<int,int>,bool>mp;
vector<int>B[maxn],b[maxn];
int N,n,k,sum,su,a1,a2,Z[maxn],z[maxn],si[maxn],be[maxn],bk[maxn],ans,l,r,f[maxn];
struct node{
	int x,y;
	bool operator<(const node &a1)const{return x>a1.x;}
}a[maxn];
void dfs(int p){
	be[p]=n;bk[p]=1;si[n]++;
	for(int i=0;i<B[p].size();i++){
		int fz=B[p][i];if(bk[fz])continue;
		if(z[n]==Z[fz])dfs(fz);
	}
	return;
}
int main(){
	freopen("green.in","r",stdin);
	freopen("green.out","w",stdout);
	scanf("%d%d",&N,&k);
	for(int i=1;i<=N;i++)scanf("%d",&Z[i]);
	for(int i=1;i<=N-1;i++){
		scanf("%d%d",&a1,&a2);
		a1++,a2++;
		B[a1].push_back(a2);
		B[a2].push_back(a1);
	}
	for(int i=1;i<=N;i++)
		if(bk[i]==0)
		    n++,z[n]=Z[i],dfs(i),a[n].x=Z[i],a[n].y=n;
	for(int i=1;i<=N;i++){
		for(int j=0;j<B[i].size();j++){
			int fz=B[i][j];
			if(be[fz]!=be[i]&&mp[make_pair(be[fz],be[i])]==0){
				b[be[fz]].push_back(be[i]);
				mp[make_pair(be[fz],be[i])]=1;
			}
		}
	}
	sort(a+1,a+1+n);memset(bk,0,sizeof(bk));
	l=r=1;while(a[r+1].x==a[l].x&&r<n)r++;
	for(int i=l;i<=r;i++){
		a1=a[i].y;
		ans=max(ans,si[a1]);
		sum+=si[a1];su++,bk[a1]=1;
	}l=r+1;
	if(sum<=k)for(;l<=n&&sum<=k;l=r+1){
		r=l;while(a[r+1].x==a[l].x&&r<n)r++;
		int fz=0;
		for(int i=l;i<=r;i++){
			a1=a[i].y;
			for(int j=0;j<b[a1].size();j++){
				a2=b[a1][j];
				if(bk[a2])f[i]++;
			}
			if(f[i]>=2){
				bk[a1]=1;sum+=si[a1];
				su+=(1-f[i]);
			}
			if(f[i]==1)fz+=si[a1];
		}
		if(su==1&&sum<=k)ans=max(ans,min(k,sum+fz));
		for(int i=l;i<=r;i++){
		    a1=a[i].y;if(bk[a1])continue;
			bk[a1]=1,sum+=si[a1],su+=(1-f[i]);
		}
		
	}
	printf("%d\n",ans);
    return 0;
}