sol

题目中操作复杂，考虑将从属关系建成三叉树以便分析。具体地，对于每次配对的三个点 $x$，$y$ 和 $z$。新建节点 $p$，代表未被配对的那个点。然后由 $p$ 向三个点连边，使得 $x$、$y$、$z$ 为 $p$ 的三个儿子。这样我们得到了一棵有根三叉树。

考虑通过树的结构重述题意：在三叉树上，由根节点开始，每次选定两个儿子向下延伸，一个权值与它相等，另一个权值大于等于它。若是叶节点，没有权值就为它赋一个权值。最终得到一棵二叉树，权值满足二叉小根堆。容易发现，根节点的权值就是所有叶子权值的最小值。

问题要使叶子的最小权值最大，考虑二分答案。设当前二分判断的值为 $val$，那么我们在所有未放的权值中找到 $\ge val$ 的，统计它们的个数。接着考虑通过树形 DP，计算最少需要放多少个 $\ge val$ 的权值，若最少需要放的数量不超过我们手上有的数量，说明答案可行。

具体地，定义 $f_u$ 表示以 $u$ 为根的子树中，最少需要放多少个。转移很简单，若 $u$ 为叶子，则：

$f_u=\begin{cases} 1 & a[u]=0\\ \infty & 0<a_u<val\\0 & a_u\ge val \end{cases}$

否则设三个儿子为 $x$，$y$，$z$，则转移方程如下：

$f_u=f_x+f_y+f_z-\max(f_x,f_y,f_z)$

也就是选择较小的两个儿子。然后就做完了，时间复杂度为 $O(n\log V)$。

闲话

我觉得我自己越练越笨了，这个症状从三月份开始，CF 连掉 200 分，一些大家都觉得很简单的贪心题总是要想很久，感觉思维链条又重又短，前途又变的一片迷茫。我也没什么好办法，打算先把蓝书过完，差的不多了，然后多做些思维训练调整状态，一步一步慢慢来，相信终有云开雾散的一天。

代码

#include <iostream>
#include <cstdio>
#include <queue>
#define int unsigned int
using namespace std;
inline int read()
{
	char c=getchar();
	int f=1,x=0;
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
inline void print(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
const int N=1e5+5,inf=1e9;
int n,m,cnt,p;
int a[N],b[N],tr[N*15][3],f[N*15];
queue<int> q;
void dfs(int u,int val)
{
	if(!tr[u][0])
	{
		if(!a[u]) f[u]=1;
		else if(a[u]>=val) f[u]=0;
		else f[u]=inf;
		return;
	}
	int x=tr[u][0],y=tr[u][1],z=tr[u][2];
	dfs(x,val);
	dfs(y,val);
	dfs(z,val);
	int mx=max(f[x],max(f[y],f[z]));
	f[u]=f[x]+f[y]+f[z]-mx;
	f[u]=min(f[u],inf);
}
inline bool check(int val)
{
	int o=0;
	for(int i=1;i<=cnt;i++) o+=(b[i]>=val);
	dfs(p,val);
	return (f[p]<=o);
}
signed main()
{
	n=read();
	m=read();
	for(int i=1;i<=m;i++)
	{
		int x,y;
		x=read();
		y=read();
		a[y]=x;
	}
	for(int i=1;i<=n-m;i++) b[++cnt]=read();
	for(int i=1;i<=n;i++) q.push(i);
	p=n;
	while(q.size()>1)
	{
		int x=q.front();
		q.pop();
		int y=q.front();
		q.pop();
		int z=q.front();
		q.pop();
		q.push(++p);
		tr[p][0]=x;
		tr[p][1]=y;
		tr[p][2]=z;
	}
	int l=1,r=1e9,ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	print(ans); 
	return 0;
}