CF627D Preorder Test

一道蛮简单的DP（然而数据很强，贼容易写挂）

先考虑DFS是如何运作的。假设当前在点$u$，那我们会选择任意一个$u$的儿子$v1$，递归搜索$v1$的子树，然后再选择一个其他的儿子$v2$进行递归搜索。显然，对于任何一个儿子的子树$v1$，我们都需要将其全部走完才能走其他儿子的子树。想到这个点这道题就很简单了。

我们二分一个最小值，对于小于这个最小值的点将其打上标记（代表不能走）。设$down[u]$代表对$u$的子树进行DFS，最多能走到多少个点。考虑如何转移状态。我们发现，如果一个子树能走的点的数目等于其子树大小（即$size[u]=down[u]$），那么我们就可以走完这个子树然后接着走其他子树。否则的话这个子树走到一半我们就必须停止整个过程。
所以转移就是这样：

int buc=0,mx=0;
rep(i,0,side[u].size()-1){//枚举u的儿子
		int v=side[u][i];if(v==fa)continue;//v为u的儿子
		dfs1(v,u);size[u]+=size[v];
		if(down[v]==size[v])buc+=size[v];
		else{
			mx=max(mx,down[v]);
		}
        if(!ban[u])down[u]=1+buc+mx;//如果u可以走，他的down值就是能走完的子树大小+不能走完子树里面最大的大小+自己的大小1
}

还有一点小问题就是，这道题的根是可以任意指定的。而我们这个做法是默认1为根的。所以当选择的根不是1时，我们可以记录一个$up$数组，把不在$u$子树内的其他点看作另外一棵子树，$up[u]$就代表了这棵子树进行DFS，最多能走到多少个点，转移方式与$down$数组类似。具体可以看代码。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=202000;
int down[maxn],up[maxn];
int a[maxn],size[maxn];
bool ban[maxn];
vi side[maxn];
multiset<int>q;
void dfs1(int u,int fa){
	size[u]=1;int buc=0,mx=0;
	rep(i,0,side[u].size()-1){
		int v=side[u][i];if(v==fa)continue;
		dfs1(v,u);size[u]+=size[v];
		if(down[v]==size[v])buc+=size[v];
		else{
			mx=max(mx,down[v]);
			q.insert(down[v]);
		}
	}
	if(!ban[u])down[u]=1+buc+mx;	
}
int n,k;
void dfs2(int u,int fa){
	q.clear();int buc=0;if(!ban[u])up[u]=max(up[u],1);
	rep(i,0,side[u].size()-1){
		int v=side[u][i];if(v==fa)continue;
		if(down[v]==size[v])buc+=size[v];
		else{
			q.insert(down[v]);
		}
	}
	if(up[u]==n-size[u]+1)buc+=up[u]-1;
	else{
			q.insert(up[u]-1);
	}
	rep(i,0,side[u].size()-1){
		int v=side[u][i];if(v==fa)continue;
		if(down[v]==size[v])buc-=size[v];
		else{
			q.erase(q.find(down[v]));
		}
		if(!ban[u]&&!ban[v]){
			up[v]=buc+((q.empty())?0:(*q.rbegin()))+2;	
		}
		if(down[v]==size[v])buc+=size[v];
		else{
			q.insert(down[v]);
		}
	}
	rep(i,0,side[u].size()-1){
		int v=side[u][i];if(v==fa)continue;
		dfs2(v,u);
	}
}
bool check(int lim){
	memset(down,0,sizeof(down));
	memset(up,0,sizeof(up));
	memset(ban,0,sizeof(ban));
	rep(i,1,n)if(a[i]<lim)ban[i]=1;
	dfs1(1,0);
	dfs2(1,0);
	rep(i,1,n){
		int ans=0;
		if(size[i]==down[i])ans=down[i]+up[i]-1;
		else if(up[i]==n-size[i]+1)ans=up[i]+down[i]-1;
		else ans=max(up[i],down[i]);
		if(ans>=k)return 1;
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>k;
	rep(i,1,n)cin>>a[i];
	rep(i,1,n-1){
		int u,v;cin>>u>>v;
		side[u].pb(v);side[v].pb(u);
	}
	int l=0,r=1000001;
	while(l<r){
		int mid=(l+r+1)>>1;
		//mid=5;
		//cout<<mid<<endl;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	cout<<l;
	return 0;
}